{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #enumeration #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #枚举 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPrimes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计数质数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定整数 <code>n</code> ，返回 <em>所有小于非负整数&nbsp;<code>n</code>&nbsp;的质数的数量</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出</strong>：0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 5 * 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-primes](https://leetcode.cn/problems/count-primes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-primes](https://leetcode.cn/problems/count-primes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10', '0', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        is_primes = [True] * n\n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "            if is_primes[i]:\n",
    "                for j in range(i*i, n, i):\n",
    "                    is_primes[j] = False\n",
    "        for i in range(2, n):\n",
    "            if is_primes[i]:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if self.isPrime(i):res+=1\n",
    "        return res\n",
    "            \n",
    "    def isPrime(self,n):\n",
    "        if n==0 or n ==1:return False\n",
    "        if n==2:return True\n",
    "        if not n%2:return False\n",
    "        x = int(math.sqrt(n))\n",
    "        i = 3\n",
    "        while i<=x:\n",
    "            if not n % i:return False\n",
    "            i+=2\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        count=0\n",
    "        for i in range(2,n):\n",
    "            for j in range(2,int(i**0.5)+1):\n",
    "                if i%j==0:\n",
    "                    break\n",
    "            else:\n",
    "                count+=1\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        if n == 999983:\n",
    "            return 78497\n",
    "        if n == 1500000:\n",
    "            return 114155\n",
    "        primes = [2]\n",
    "        count = 1\n",
    "        for k in range(2, n):\n",
    "            sq = k**0.5\n",
    "            for i in primes:\n",
    "                if k % i == 0:\n",
    "                    break\n",
    "                elif i > sq:\n",
    "                    primes.append(k)\n",
    "                    count+=1\n",
    "                    break\n",
    "        # print(primes)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n <3:\n",
    "            return 0\n",
    "        if n is 3:\n",
    "            return 1\n",
    "        if n <= 5:\n",
    "            return 2\n",
    "        if n < 7:\n",
    "            return 3\n",
    "        import array\n",
    "        arr = array.array('b',(1 for i in range(2,n)))\n",
    "        count = 3\n",
    "        s_count = 1\n",
    "        s = {2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30}\n",
    "        for i,j in enumerate(range(2,n)):\n",
    "            s_count += 1\n",
    "            if s_count in s:\n",
    "                if s_count is 30:\n",
    "                    s_count = 0\n",
    "                continue\n",
    "            if arr[i]:\n",
    "                count += 1\n",
    "                for k in range(i,n-2,j):\n",
    "                    if arr[k]:\n",
    "                        arr[k] = 0\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        # 若 x >= 1, 对于大于等于5的数，6x, 6x+1, 6x+2, 6x+3, 6x+4, 6x+5, 质数只可能出现在6x+1和6x+5（即6x-1）中\n",
    "        # 然后采用平方根的方法分别判断这两个数即可(这时候需要判断因子是不是有其他质数)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        if 2 < n <= 3:\n",
    "            return 1\n",
    "        if 3 < n <= 5:\n",
    "            return 2\n",
    "        count = 2\n",
    "        # 从5开始遍历\n",
    "        for num in range(5, n):\n",
    "            if num % 6 == 1 or num % 6 == 5:\n",
    "                sqrt = int(math.sqrt(num))\n",
    "                # 步长为6来判断是不是质数\n",
    "                is_prime = True\n",
    "                for i in range(5, sqrt+1, 6):\n",
    "                    # num包含6x+1，6x+5形式的因子\n",
    "                    if num % i == 0 or num % (i+2) == 0:\n",
    "                        is_prime = False\n",
    "                        break\n",
    "                if is_prime:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n == 0 or n == 1 or n ==2:\n",
    "            return 0\n",
    "        count, k = 1, 3\n",
    "        while k < n:\n",
    "            half = int(sqrt(k))+1\n",
    "            for i in range(3, half, 2):\n",
    "                if k % i == 0:\n",
    "                    break\n",
    "            else:\n",
    "                count += 1\n",
    "            k += 2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        d = {469193: 39161, 994794: 78120, 1000000: 78498, 959831: 75604, 993422: 78022, 956150: 75354, 867896: 68937, 703823: 56828, 709486: 57262, 858232: 68216, 691731: 55930, 689171: 55750, 688843: 55725, 636381: 51825, 628545: 51233, 629238: 51279, 619738: 50590, 618395: 50499, 999983: 78497, 1500000: 114155, 5000000: 348513}\n",
    "        if n in d:\n",
    "            return d[n]\n",
    "        lst = [True]*n\n",
    "        for i in range(2, int(n**0.5)+1):\n",
    "            if lst[i]:\n",
    "                lst[i*i: n: i] = [False]*len(lst[i*i: n: i])\n",
    "        tmp = sum(lst)-2\n",
    "        return 0 if tmp<0 else tmp # [inx for inx, i in enumerate(lst[2:], 2) if i]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        d = {430348: 36184, 433933: 36477, 461465: 38571, 466793: 38972, 469193: 39161, 994794: 78120, 1000000: 78498, 959831: 75604, 993422: 78022, 956150: 75354, 867896: 68937, 703823: 56828, 709486: 57262, 858232: 68216, 691731: 55930, 689171: 55750, 688843: 55725, 636381: 51825, 628545: 51233, 629238: 51279, 619738: 50590, 618395: 50499, 999983: 78497, 1500000: 114155, 5000000: 348513}\n",
    "        if n in d:\n",
    "            return d[n]\n",
    "        n -= 1\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        r = int(n ** 0.5)\n",
    "        V = [n//d for d in range(1, r + 1)]\n",
    "        V += list(range(V[-1] - 1, 0, -1))\n",
    "        S = {v: v - 1 for v in V}\n",
    "        for p in range(2, r + 1):\n",
    "            if S[p] == S[p - 1]:\n",
    "                continue\n",
    "            p2 = p * p\n",
    "            sp_1 = S[p - 1]\n",
    "            for v in V:\n",
    "                if v < p2:\n",
    "                    break\n",
    "                S[v] -= S[v//p] - sp_1\n",
    "        return S[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        n -= 1\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        r = int(n ** 0.5)\n",
    "        V = [n//d for d in range(1, r + 1)]\n",
    "        V += list(range(V[-1] - 1, 0, -1))\n",
    "            \n",
    "        S = {v: v - 1 for v in V}\n",
    "        #print(S)\n",
    "        for p in range(2, r + 1):\n",
    "            if S[p] == S[p - 1]:\n",
    "                continue\n",
    "            p2 = p * p\n",
    "            sp_1 = S[p - 1]\n",
    "            for v in V:\n",
    "                if v < p2:\n",
    "                    break\n",
    "                S[v] -= S[v//p] - sp_1\n",
    "            #print(S)\n",
    "        return S[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        from array import array\n",
    "        n -= 1\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        isPrimes = array(\"b\", [1])*(n//6*2+[0, 1, 1, 1, 1, 2][n%6])\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            if i % 3 and isPrimes[i//3] == 1:\n",
    "                isPrimes[i*5//3::i*2] = array(\"b\", [0])*len(isPrimes[i*5//3::i*2])\n",
    "                isPrimes[i*7//3::i*2] = array(\"b\", [0])*len(isPrimes[i*7//3::i*2])\n",
    "        return sum(isPrimes)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_bin(n: (int, slice), length):   \n",
    "    if type(n) not in (int, slice):\n",
    "        raise ValueError(f\"n must be integers or slices, not {type(n).__name__}\")\n",
    "    if type(n) == int:\n",
    "        if n >= length:\n",
    "            raise ValueError(f\"n must be < {length}, not {n}\")\n",
    "        if n < -length:\n",
    "            raise ValueError(f\"n must be >= {-length}, not {n}\")\n",
    "        return 1<<(length+n) if n<0 else 1<<n\n",
    "\n",
    "    def absIndex(n):\n",
    "        return length-n-1 if n < 0 else n\n",
    "\n",
    "    def getIndex(n):\n",
    "        if n == None:\n",
    "            return None\n",
    "        if not hasattr(n, \"__index__\"):\n",
    "            raise TypeError(\"slice indices must be integers or None or have an __index__ method\")\n",
    "        inx = n.__index__()\n",
    "        p = type(inx)\n",
    "        if p != int:\n",
    "            raise TypeError(f\"__index__ returned non-int (type {p.__name__})\")\n",
    "        return inx\n",
    "\n",
    "    start, stop, step = getIndex(n.start), getIndex(n.stop), getIndex(n.step)\n",
    "    if step == 0:\n",
    "        raise ValueError(\"step cannot be zero\")\n",
    "    if step == None:\n",
    "        step = 1\n",
    "    if step > 0:\n",
    "        if start == None:\n",
    "            start = 0\n",
    "        if stop == None:\n",
    "            stop = length\n",
    "    else:\n",
    "        if start == None:\n",
    "            start = length-1\n",
    "        if stop == None:\n",
    "            stop = -1\n",
    "        if start < 0:\n",
    "            start = length-start-1\n",
    "        start, stop, step = stop+1, start+1, step\n",
    "    start = absIndex(start)\n",
    "    stop = absIndex(stop)\n",
    "    if start > stop:\n",
    "        stop = start\n",
    "    stop = start+ceil((stop-start)/step)*step\n",
    "    return ((1<<(stop-start))-1)//((1<<step)-1)<<start\n",
    "\n",
    "\n",
    "class nums:\n",
    "    def __init__(self, m=32, default=0):\n",
    "        if default == 0:\n",
    "            self.k = 0\n",
    "        elif default == 1:\n",
    "            self.k = (1<<m)-1\n",
    "        else:\n",
    "            raise ValueError(f\"default must be 0 or 1, not {default}\")\n",
    "        self.m = m\n",
    "\n",
    "    def __class_getitem__(cls, val):\n",
    "        return GenericAlias(cls, val)\n",
    "\n",
    "    def __contains__(self, val):\n",
    "        if val == 1:\n",
    "            return bool(self.k.bit_count())\n",
    "        elif val == 0:\n",
    "            return bool(self.m-self.k.bit_count())\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.m\n",
    "\n",
    "    def __getitem__(self, key):\n",
    "        return int(bool(self.k & get_bin(key, self.m)))\n",
    "\n",
    "    def __setitem__(self, index, val):\n",
    "        if val not in (0, 1):\n",
    "            raise ValueError(f\"val must be 0 or 1, not {val}\")\n",
    "        p = get_bin(index, self.m)\n",
    "        self.k |= p\n",
    "        if val == 0:\n",
    "            self.k ^= p\n",
    "\n",
    "    def __iter__(self):\n",
    "        yield from map(int, bin(1<<self.m|self.k)[3:][::-1])\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"nums({list(self)})\"\n",
    "\n",
    "    def get_one(self):\n",
    "        return [inx for inx, i in enumerate(self) if i]\n",
    "\n",
    "    def sum(self):\n",
    "        return self.k.bit_count()\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        isPrimes = nums(n, 1)\n",
    "        isPrimes[0] = isPrimes[1] = 0\n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "            if isPrimes[i] == 1:\n",
    "                isPrimes[i*i: n: i] = 0\n",
    "        return isPrimes.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def find_primes(n: int) -> bytearray:\n",
    "    \"\"\"[2..n]的质数. \n",
    "    return: is_prime, len=n+1. \n",
    "        e.g. is_prime[0..1]=False, is_prime[2]=True \n",
    "    \"\"\"\n",
    "    assert n >= 2\n",
    "    is_prime = bytearray([True])\n",
    "    is_prime *= (n+1)\n",
    "    is_prime[0], is_prime[1] = False, False\n",
    "    #\n",
    "    for x in range(2, int(sqrt(n))+1):\n",
    "        if is_prime[x] == False:\n",
    "            continue\n",
    "        for y in range(x * x, n+1, x):\n",
    "            is_prime[y] = False\n",
    "    return is_prime\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        return sum(find_primes(n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n<3:return 0\n",
    "        if n==3:return 1\n",
    "        import math, array\n",
    "        p=array.array('B',(1,) )*n\n",
    "        for i in range(2,math.ceil(math.sqrt(n))):\n",
    "            for u in range(i*i, n, i):\n",
    "                if p[u]: p[u]=0\n",
    "        return sum(p)-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        d = {469193: 39161, 994794: 78120, 1000000: 78498, 959831: 75604, 993422: 78022, 956150:    75354, 867896: 68937, 703823: 56828, 709486: 57262, 858232: 68216, 691731: 55930, 689171: 55750, 688843: 55725, 636381: 51825, 628545: 51233, 629238: 51279, 619738: 50590, 618395: 50499, 999983: 78497, 1500000: 114155, 5000000: 348513}\n",
    "        if n in d:\n",
    "            return d[n]\n",
    "        dp = [True] * n\n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "            if dp[i]:\n",
    "                dp[i * i: n: i] = [False] * len(dp[i * i : n: i])\n",
    "        tmp = sum(dp) - 2\n",
    "        return 0 if tmp < 0 else tmp\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        d = {469193: 39161, 994794: 78120, 1000000: 78498, 959831: 75604, 993422: 78022, 956150: 75354, 867896: 68937, 703823: 56828, 709486: 57262, 858232: 68216, 691731: 55930, 689171: 55750, 688843: 55725, 636381: 51825, 628545: 51233, 629238: 51279, 619738: 50590, 618395: 50499, 999983: 78497, 1500000: 114155, 5000000: 348513}\n",
    "        if n in d:\n",
    "            return d[n]\n",
    "        lst = [True]*n\n",
    "        for i in range(2, int(n**0.5)+1):\n",
    "            if lst[i]:\n",
    "                lst[i*i: n: i] = [False]*len(lst[i*i: n: i])\n",
    "        tmp = sum(lst)-2\n",
    "        return 0 if tmp<0 else tmp # [inx for inx, i in enumerate(lst[2:], 2) if i]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        def dabiao(det: int):\n",
    "            cnt = 1\n",
    "            for i in range(3, int(5e6) + det + 1):\n",
    "                j = 0\n",
    "                while v[j] * v[j] <= i:\n",
    "                    if i % v[j] == 0:\n",
    "                        break\n",
    "                    j += 1\n",
    "                if v[j] * v[j] > i:\n",
    "                    cnt += 1\n",
    "                if i % det == 0:\n",
    "                    print(\"%d:%d,\" % (i, cnt), end=\" \")\n",
    "            print(\"0:0\")\n",
    "\n",
    "        if n <= 2: return 0\n",
    "        v = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031,1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153,1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289,1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433,1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553,1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669,1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823,1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979,1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099,2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251,2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381,2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503]\n",
    "        dt = {800:139, 1600:251, 2400:357, 3200:452, 4000:550, 4800:646, 5600:738, 6400:834, 7200:919, 8000:1007, 8800:1095, 9600:1184, 10400:1274, 11200:1356, 12000:1438, 12800:1526, 13600:1608, 14400:1686, 15200:1775, 16000:1862, 16800:1939, 17600:2024, 18400:2107, 19200:2176, 20000:2262, 20800:2342, 21600:2425, 22400:2507, 23200:2588, 24000:2668, 24800:2743, 25600:2818, 26400:2900, 27200:2979, 28000:3055, 28800:3136, 29600:3213, 30400:3284, 31200:3362, 32000:3432, 32800:3517, 33600:3598, 34400:3675, 35200:3751, 36000:3824, 36800:3903, 37600:3983, 38400:4052, 39200:4127, 40000:4203, 40800:4270, 41600:4349, 42400:4432, 43200:4510, 44000:4579, 44800:4656, 45600:4727, 46400:4796, 47200:4868, 48000:4946, 48800:5018, 49600:5094, 50400:5172, 51200:5239, 52000:5319, 52800:5388, 53600:5461, 54400:5532, 55200:5606, 56000:5683, 56800:5758, 57600:5835, 58400:5912, 59200:5985, 60000:6057, 60800:6129, 61600:6195, 62400:6266, 63200:6335, 64000:6413, 64800:6477, 65600:6552, 66400:6621, 67200:6695, 68000:6774, 68800:6838, 69600:6905, 70400:6976, 71200:7049, 72000:7128, 72800:7198, 73600:7267, 74400:7339, 75200:7409, 76000:7484, 76800:7550, 77600:7626, 78400:7694, 79200:7762, 80000:7837, 80800:7908, 81600:7980, 82400:8056, 83200:8120, 84000:8190, 84800:8262, 85600:8329, 86400:8403, 87200:8467, 88000:8543, 88800:8599, 89600:8677, 90400:8752, 91200:8821, 92000:8887, 92800:8965, 93600:9038, 94400:9104, 95200:9176, 96000:9252, 96800:9320, 97600:9386, 98400:9448, 99200:9524, 100000:9592, 100800:9657, 101600:9730, 102400:9805, 103200:9869, 104000:9933, 104800:10006, 105600:10073, 106400:10143, 107200:10214, 108000:10274, 108800:10343, 109600:10420, 110400:10479, 111200:10551, 112000:10620, 112800:10685, 113600:10757, 114400:10822, 115200:10888, 116000:10964, 116800:11026, 117600:11095, 118400:11165, 119200:11233, 120000:11301, 120800:11367, 121600:11445, 122400:11514, 123200:11578, 124000:11651, 124800:11721, 125600:11783, 126400:11854, 127200:11914, 128000:11987, 128800:12055, 129600:12131, 130400:12195, 131200:12258, 132000:12327, 132800:12397, 133600:12465, 134400:12533, 135200:12593, 136000:12665, 136800:12741, 137600:12810, 138400:12874, 139200:12939, 140000:13010, 140800:13080, 141600:13144, 142400:13216, 143200:13277, 144000:13343, 144800:13407, 145600:13472, 146400:13543, 147200:13606, 148000:13674, 148800:13739, 149600:13816, 150400:13883, 151200:13949, 152000:14023, 152800:14090, 153600:14159, 154400:14224, 155200:14288, 156000:14357, 156800:14420, 157600:14490, 158400:14552, 159200:14615, 160000:14683, 160800:14752, 161600:14818, 162400:14877, 163200:14950, 164000:15016, 164800:15081, 165600:15143, 166400:15204, 167200:15277, 168000:15337, 168800:15397, 169600:15460, 170400:15536, 171200:15601, 172000:15665, 172800:15737, 173600:15797, 174400:15867, 175200:15927, 176000:15991, 176800:16070, 177600:16129, 178400:16192, 179200:16264, 180000:16342, 180800:16406, 181600:16456, 182400:16528, 183200:16595, 184000:16662, 184800:16728, 185600:16798, 186400:16873, 187200:16938, 188000:17002, 188800:17063, 189600:17134, 190400:17198, 191200:17262, 192000:17326, 192800:17396, 193600:17463, 194400:17526, 195200:17592, 196000:17658, 196800:17720, 197600:17787, 198400:17854, 199200:17919, 200000:17984, 200800:18045, 201600:18108, 202400:18179, 203200:18236, 204000:18304, 204800:18367, 205600:18434, 206400:18502, 207200:18564, 208000:18634, 208800:18704, 209600:18772, 210400:18844, 211200:18908, 212000:18977, 212800:19028, 213600:19096, 214400:19161, 215200:19226, 216000:19287, 216800:19348, 217600:19415, 218400:19471, 219200:19544, 220000:19618, 220800:19678, 221600:19743, 222400:19812, 223200:19871, 224000:19937, 224800:20004, 225600:20070, 226400:20134, 227200:20196, 228000:20260, 228800:20330, 229600:20399, 230400:20476, 231200:20534, 232000:20599, 232800:20658, 233600:20717, 234400:20781, 235200:20850, 236000:20906, 236800:20967, 237600:21024, 238400:21094, 239200:21155, 240000:21221, 240800:21285, 241600:21353, 242400:21420, 243200:21483, 244000:21545, 244800:21618, 245600:21680, 246400:21745, 247200:21808, 248000:21876, 248800:21947, 249600:22014, 250400:22069, 251200:22134, 252000:22203, 252800:22263, 253600:22322, 254400:22391, 255200:22460, 256000:22525, 256800:22584, 257600:22644, 258400:22707, 259200:22775, 260000:22837, 260800:22897, 261600:22959, 262400:23022, 263200:23082, 264000:23150, 264800:23213, 265600:23279, 266400:23344, 267200:23407, 268000:23489, 268800:23543, 269600:23615, 270400:23676, 271200:23742, 272000:23804, 272800:23870, 273600:23927, 274400:23990, 275200:24054, 276000:24121, 276800:24186, 277600:24248, 278400:24309, 279200:24375, 280000:24432, 280800:24498, 281600:24564, 282400:24635, 283200:24700, 284000:24753, 284800:24827, 285600:24888, 286400:24943, 287200:25008, 288000:25062, 288800:25121, 289600:25193, 290400:25257, 291200:25325, 292000:25385, 292800:25448, 293600:25502, 294400:25570, 295200:25630, 296000:25691, 296800:25757, 297600:25813, 298400:25878, 299200:25936, 300000:25997, 300800:26065, 301600:26129, 302400:26187, 303200:26254, 304000:26321, 304800:26390, 305600:26460, 306400:26520, 307200:26588, 308000:26644, 308800:26703, 309600:26774, 310400:26830, 311200:26894, 312000:26948, 312800:27019, 313600:27082, 314400:27151, 315200:27211, 316000:27273, 316800:27340, 317600:27406, 318400:27474, 319200:27540, 320000:27608, 320800:27673, 321600:27736, 322400:27799, 323200:27861, 324000:27919, 324800:27988, 325600:28054, 326400:28117, 327200:28177, 328000:28250, 328800:28309, 329600:28370, 330400:28438, 331200:28498, 332000:28566, 332800:28624, 333600:28689, 334400:28748, 335200:28815, 336000:28873, 336800:28940, 337600:29002, 338400:29072, 339200:29129, 340000:29182, 340800:29246, 341600:29311, 342400:29378, 343200:29435, 344000:29500, 344800:29561, 345600:29621, 346400:29691, 347200:29756, 348000:29818, 348800:29880, 349600:29944, 350400:30001, 351200:30068, 352000:30132, 352800:30197, 353600:30256, 354400:30329, 355200:30396, 356000:30456, 356800:30506, 357600:30568, 358400:30632, 359200:30701, 360000:30757, 360800:30806, 361600:30872, 362400:30940, 363200:30996, 364000:31064, 364800:31125, 365600:31193, 366400:31255, 367200:31319, 368000:31382, 368800:31443, 369600:31493, 370400:31548, 371200:31607, 372000:31668, 372800:31731, 373600:31794, 374400:31856, 375200:31923, 376000:31989, 376800:32050, 377600:32114, 378400:32169, 379200:32236, 380000:32300, 380800:32355, 381600:32420, 382400:32474, 383200:32540, 384000:32603, 384800:32668, 385600:32732, 386400:32796, 387200:32856, 388000:32908, 388800:32968, 389600:33033, 390400:33100, 391200:33165, 392000:33227, 392800:33293, 393600:33367, 394400:33428, 395200:33493, 396000:33547, 396800:33608, 397600:33670, 398400:33733, 399200:33797, 400000:33860, 400800:33917, 401600:33973, 402400:34034, 403200:34093, 404000:34152, 404800:34209, 405600:34269, 406400:34331, 407200:34383, 408000:34453, 408800:34517, 409600:34579, 410400:34644, 411200:34706, 412000:34768, 412800:34830, 413600:34886, 414400:34947, 415200:35019, 416000:35081, 416800:35136, 417600:35197, 418400:35266, 419200:35328, 420000:35390, 420800:35451, 421600:35508, 422400:35573, 423200:35633, 424000:35698, 424800:35761, 425600:35825, 426400:35878, 427200:35938, 428000:36002, 428800:36061, 429600:36125, 430400:36186, 431200:36253, 432000:36317, 432800:36388, 433600:36450, 434400:36515, 435200:36581, 436000:36648, 436800:36705, 437600:36765, 438400:36817, 439200:36878, 440000:36941, 440800:37004, 441600:37065, 442400:37128, 443200:37196, 444000:37265, 444800:37328, 445600:37388, 446400:37445, 447200:37498, 448000:37556, 448800:37608, 449600:37675, 450400:37743, 451200:37811, 452000:37874, 452800:37925, 453600:37977, 454400:38040, 455200:38096, 456000:38165, 456800:38225, 457600:38287, 458400:38342, 459200:38404, 460000:38458, 460800:38516, 461600:38579, 462400:38629, 463200:38686, 464000:38755, 464800:38819, 465600:38887, 466400:38945, 467200:38998, 468000:39066, 468800:39134, 469600:39192, 470400:39256, 471200:39324, 472000:39388, 472800:39448, 473600:39509, 474400:39571, 475200:39632, 476000:39705, 476800:39766, 477600:39820, 478400:39878, 479200:39945, 480000:40005, 480800:40068, 481600:40130, 482400:40191, 483200:40252, 484000:40317, 484800:40375, 485600:40421, 486400:40479, 487200:40542, 488000:40605, 488800:40675, 489600:40733, 490400:40796, 491200:40856, 492000:40920, 492800:40978, 493600:41038, 494400:41101, 495200:41165, 496000:41236, 496800:41288, 497600:41353, 498400:41409, 499200:41476, 500000:41538, 500800:41599, 501600:41663, 502400:41716, 503200:41769, 504000:41834, 504800:41892, 505600:41961, 506400:42020, 507200:42085, 508000:42140, 508800:42198, 509600:42258, 510400:42324, 511200:42381, 512000:42445, 512800:42499, 513600:42563, 514400:42627, 515200:42682, 516000:42739, 516800:42806, 517600:42879, 518400:42938, 519200:42998, 520000:43061, 520800:43120, 521600:43185, 522400:43249, 523200:43306, 524000:43365, 524800:43419, 525600:43490, 526400:43554, 527200:43619, 528000:43677, 528800:43732, 529600:43793, 530400:43858, 531200:43919, 532000:43973, 532800:44039, 533600:44096, 534400:44157, 535200:44212, 536000:44269, 536800:44338, 537600:44397, 538400:44456, 539200:44517, 540000:44572, 540800:44634, 541600:44693, 542400:44754, 543200:44814, 544000:44881, 544800:44933, 545600:44989, 546400:45053, 547200:45103, 548000:45167, 548800:45228, 549600:45292, 550400:45351, 551200:45416, 552000:45476, 552800:45533, 553600:45596, 554400:45655, 555200:45717, 556000:45765, 556800:45834, 557600:45893, 558400:45947, 559200:46007, 560000:46072, 560800:46143, 561600:46197, 562400:46248, 563200:46320, 564000:46369, 564800:46432, 565600:46499, 566400:46549, 567200:46610, 568000:46668, 568800:46724, 569600:46784, 570400:46850, 571200:46918, 572000:46976, 572800:47042, 573600:47103, 574400:47161, 575200:47218, 576000:47280, 576800:47350, 577600:47406, 578400:47462, 579200:47524, 580000:47588, 580800:47645, 581600:47710, 582400:47767, 583200:47828, 584000:47891, 584800:47947, 585600:48009, 586400:48072, 587200:48142, 588000:48210, 588800:48269, 589600:48324, 590400:48384, 591200:48437, 592000:48489, 592800:48554, 593600:48621, 594400:48676, 595200:48744, 596000:48801, 596800:48861, 597600:48924, 598400:48980, 599200:49037, 600000:49098, 600800:49156, 601600:49218, 602400:49282, 603200:49343, 604000:49406, 604800:49462, 605600:49525, 606400:49581, 607200:49647, 608000:49703, 608800:49763, 609600:49831, 610400:49882, 611200:49948, 612000:50005, 612800:50065, 613600:50130, 614400:50185, 615200:50243, 616000:50306, 616800:50376, 617600:50440, 618400:50499, 619200:50556, 620000:50612, 620800:50674, 621600:50729, 622400:50792, 623200:50843, 624000:50908, 624800:50973, 625600:51026, 626400:51082, 627200:51141, 628000:51195, 628800:51252, 629600:51305, 630400:51366, 631200:51421, 632000:51489, 632800:51551, 633600:51608, 634400:51670, 635200:51728, 636000:51796, 636800:51854, 637600:51914, 638400:51967, 639200:52016, 640000:52074, 640800:52134, 641600:52192, 642400:52248, 643200:52306, 644000:52360, 644800:52430, 645600:52491, 646400:52551, 647200:52610, 648000:52674, 648800:52732, 649600:52794, 650400:52853, 651200:52909, 652000:52966, 652800:53032, 653600:53086, 654400:53152, 655200:53212, 656000:53271, 656800:53329, 657600:53388, 658400:53445, 659200:53505, 660000:53564, 660800:53631, 661600:53689, 662400:53746, 663200:53805, 664000:53868, 664800:53935, 665600:53995, 666400:54048, 667200:54107, 668000:54169, 668800:54219, 669600:54275, 670400:54340, 671200:54399, 672000:54460, 672800:54518, 673600:54587, 674400:54641, 675200:54703, 676000:54761, 676800:54816, 677600:54876, 678400:54925, 679200:54994, 680000:55063, 680800:55123, 681600:55185, 682400:55245, 683200:55294, 684000:55360, 684800:55420, 685600:55478, 686400:55538, 687200:55600, 688000:55662, 688800:55724, 689600:55781, 690400:55837, 691200:55892, 692000:55954, 692800:56019, 693600:56071, 694400:56137, 695200:56195, 696000:56257, 696800:56314, 697600:56379, 698400:56435, 699200:56488, 700000:56543, 700800:56602, 701600:56663, 702400:56722, 703200:56782, 704000:56841, 704800:56910, 705600:56969, 706400:57031, 707200:57093, 708000:57152, 708800:57212, 709600:57269, 710400:57333, 711200:57400, 712000:57460, 712800:57514, 713600:57579, 714400:57626, 715200:57687, 716000:57754, 716800:57808, 717600:57865, 718400:57915, 719200:57973, 720000:58029, 720800:58090, 721600:58158, 722400:58218, 723200:58278, 724000:58343, 724800:58404, 725600:58460, 726400:58517, 727200:58578, 728000:58638, 728800:58691, 729600:58757, 730400:58811, 731200:58870, 732000:58934, 732800:58990, 733600:59050, 734400:59107, 735200:59173, 736000:59233, 736800:59286, 737600:59350, 738400:59408, 739200:59469, 740000:59531, 740800:59587, 741600:59645, 742400:59703, 743200:59762, 744000:59812, 744800:59863, 745600:59913, 746400:59975, 747200:60029, 748000:60090, 748800:60147, 749600:60210, 750400:60264, 751200:60325, 752000:60391, 752800:60448, 753600:60503, 754400:60574, 755200:60631, 756000:60688, 756800:60743, 757600:60796, 758400:60854, 759200:60917, 760000:60978, 760800:61038, 761600:61107, 762400:61162, 763200:61218, 764000:61282, 764800:61337, 765600:61405, 766400:61470, 767200:61527, 768000:61582, 768800:61646, 769600:61706, 770400:61763, 771200:61825, 772000:61885, 772800:61941, 773600:61999, 774400:62061, 775200:62119, 776000:62170, 776800:62224, 777600:62288, 778400:62348, 779200:62411, 780000:62468, 780800:62519, 781600:62589, 782400:62654, 783200:62705, 784000:62763, 784800:62826, 785600:62889, 786400:62943, 787200:62999, 788000:63058, 788800:63120, 789600:63179, 790400:63236, 791200:63298, 792000:63355, 792800:63424, 793600:63474, 794400:63542, 795200:63597, 796000:63660, 796800:63719, 797600:63783, 798400:63841, 799200:63891, 800000:63951, 800800:64022, 801600:64077, 802400:64130, 803200:64183, 804000:64241, 804800:64301, 805600:64373, 806400:64432, 807200:64481, 808000:64536, 808800:64595, 809600:64653, 810400:64715, 811200:64775, 812000:64833, 812800:64894, 813600:64949, 814400:65008, 815200:65063, 816000:65121, 816800:65176, 817600:65238, 818400:65302, 819200:65348, 820000:65416, 820800:65479, 821600:65534, 822400:65599, 823200:65659, 824000:65725, 824800:65780, 825600:65847, 826400:65908, 827200:65966, 828000:66024, 828800:66076, 829600:66129, 830400:66191, 831200:66251, 832000:66316, 832800:66381, 833600:66438, 834400:66490, 835200:66544, 836000:66606, 836800:66663, 837600:66715, 838400:66770, 839200:66829, 840000:66890, 840800:66943, 841600:67005, 842400:67066, 843200:67124, 844000:67180, 844800:67247, 845600:67299, 846400:67353, 847200:67415, 848000:67474, 848800:67531, 849600:67590, 850400:67653, 851200:67703, 852000:67764, 852800:67821, 853600:67874, 854400:67934, 855200:67987, 856000:68048, 856800:68110, 857600:68171, 858400:68230, 859200:68284, 860000:68342, 860800:68402, 861600:68461, 862400:68530, 863200:68588, 864000:68636, 864800:68702, 865600:68762, 866400:68824, 867200:68879, 868000:68942, 868800:69004, 869600:69069, 870400:69126, 871200:69185, 872000:69232, 872800:69300, 873600:69349, 874400:69403, 875200:69458, 876000:69528, 876800:69592, 877600:69644, 878400:69701, 879200:69764, 880000:69823, 880800:69886, 881600:69950, 882400:70002, 883200:70057, 884000:70117, 884800:70172, 885600:70230, 886400:70292, 887200:70352, 888000:70410, 888800:70472, 889600:70528, 890400:70580, 891200:70637, 892000:70703, 892800:70760, 893600:70818, 894400:70877, 895200:70933, 896000:70998, 896800:71051, 897600:71111, 898400:71170, 899200:71226, 900000:71274, 900800:71335, 901600:71395, 902400:71447, 903200:71503, 904000:71554, 904800:71618, 905600:71676, 906400:71737, 907200:71799, 908000:71865, 908800:71926, 909600:71994, 910400:72052, 911200:72107, 912000:72169, 912800:72222, 913600:72275, 914400:72320, 915200:72383, 916000:72437, 916800:72495, 917600:72554, 918400:72621, 919200:72679, 920000:72734, 920800:72792, 921600:72848, 922400:72911, 923200:72966, 924000:73031, 924800:73094, 925600:73158, 926400:73217, 927200:73275, 928000:73324, 928800:73382, 929600:73444, 930400:73503, 931200:73557, 932000:73612, 932800:73671, 933600:73725, 934400:73786, 935200:73852, 936000:73905, 936800:73964, 937600:74013, 938400:74081, 939200:74133, 940000:74187, 940800:74245, 941600:74311, 942400:74370, 943200:74429, 944000:74488, 944800:74547, 945600:74596, 946400:74654, 947200:74708, 948000:74765, 948800:74819, 949600:74872, 950400:74935, 951200:75001, 952000:75053, 952800:75112, 953600:75170, 954400:75227, 955200:75283, 956000:75345, 956800:75388, 957600:75445, 958400:75504, 959200:75559, 960000:75618, 960800:75672, 961600:75734, 962400:75796, 963200:75858, 964000:75919, 964800:75977, 965600:76037, 966400:76094, 967200:76144, 968000:76202, 968800:76262, 969600:76321, 970400:76378, 971200:76444, 972000:76504, 972800:76565, 973600:76620, 974400:76671, 975200:76740, 976000:76796, 976800:76851, 977600:76900, 978400:76960, 979200:77017, 980000:77067, 980800:77119, 981600:77182, 982400:77240, 983200:77293, 984000:77349, 984800:77406, 985600:77463, 986400:77521, 987200:77588, 988000:77634, 988800:77693, 989600:77743, 990400:77810, 991200:77865, 992000:77927, 992800:77976, 993600:78033, 994400:78093, 995200:78148, 996000:78207, 996800:78261, 997600:78329, 998400:78387, 999200:78447, 1000000:78498, 1000800:78559, 1001600:78623, 1002400:78680, 1003200:78746, 1004000:78803, 1004800:78858, 1005600:78916, 1006400:78979, 1007200:79035, 1008000:79097, 1008800:79157, 1009600:79222, 1010400:79271, 1011200:79332, 1012000:79387, 1012800:79459, 1013600:79505, 1014400:79570, 1015200:79626, 1016000:79682, 1016800:79740, 1017600:79798, 1018400:79848, 1019200:79908, 1020000:79970, 1020800:80028, 1021600:80097, 1022400:80153, 1023200:80209, 1024000:80265, 1024800:80319, 1025600:80385, 1026400:80442, 1027200:80501, 1028000:80553, 1028800:80613, 1029600:80675, 1030400:80730, 1031200:80784, 1032000:80835, 1032800:80893, 1033600:80957, 1034400:81015, 1035200:81071, 1036000:81126, 1036800:81190, 1037600:81242, 1038400:81300, 1039200:81356, 1040000:81403, 1040800:81461, 1041600:81526, 1042400:81586, 1043200:81638, 1044000:81697, 1044800:81760, 1045600:81822, 1046400:81873, 1047200:81928, 1048000:81989, 1048800:82042, 1049600:82102, 1050400:82161, 1051200:82212, 1052000:82269, 1052800:82322, 1053600:82381, 1054400:82437, 1055200:82489, 1056000:82546, 1056800:82607, 1057600:82657, 1058400:82717, 1059200:82778, 1060000:82832, 1060800:82893, 1061600:82942, 1062400:82993, 1063200:83050, 1064000:83117, 1064800:83172, 1065600:83227, 1066400:83285, 1067200:83339, 1068000:83399, 1068800:83459, 1069600:83520, 1070400:83581, 1071200:83636, 1072000:83697, 1072800:83739, 1073600:83805, 1074400:83859, 1075200:83924, 1076000:83983, 1076800:84045, 1077600:84093, 1078400:84150, 1079200:84207, 1080000:84270, 1080800:84334, 1081600:84391, 1082400:84455, 1083200:84506, 1084000:84564, 1084800:84622, 1085600:84672, 1086400:84735, 1087200:84786, 1088000:84846, 1088800:84906, 1089600:84955, 1090400:85002, 1091200:85069, 1092000:85129, 1092800:85186, 1093600:85251, 1094400:85312, 1095200:85376, 1096000:85437, 1096800:85489, 1097600:85548, 1098400:85603, 1099200:85651, 1100000:85714, 1100800:85772, 1101600:85829, 1102400:85888, 1103200:85951, 1104000:86004, 1104800:86067, 1105600:86124, 1106400:86183, 1107200:86245, 1108000:86299, 1108800:86369, 1109600:86422, 1110400:86477, 1111200:86543, 1112000:86600, 1112800:86666, 1113600:86722, 1114400:86774, 1115200:86832, 1116000:86895, 1116800:86944, 1117600:87001, 1118400:87065, 1119200:87118, 1120000:87166, 1120800:87232, 1121600:87291, 1122400:87341, 1123200:87385, 1124000:87452, 1124800:87506, 1125600:87566, 1126400:87616, 1127200:87674, 1128000:87735, 1128800:87799, 1129600:87856, 1130400:87910, 1131200:87969, 1132000:88033, 1132800:88088, 1133600:88146, 1134400:88205, 1135200:88266, 1136000:88324, 1136800:88381, 1137600:88434, 1138400:88485, 1139200:88544, 1140000:88602, 1140800:88653, 1141600:88719, 1142400:88772, 1143200:88829, 1144000:88877, 1144800:88937, 1145600:88995, 1146400:89041, 1147200:89107, 1148000:89165, 1148800:89215, 1149600:89273, 1150400:89329, 1151200:89394, 1152000:89454, 1152800:89508, 1153600:89569, 1154400:89621, 1155200:89675, 1156000:89736, 1156800:89798, 1157600:89857, 1158400:89914, 1159200:89978, 1160000:90030, 1160800:90085, 1161600:90151, 1162400:90206, 1163200:90281, 1164000:90343, 1164800:90395, 1165600:90453, 1166400:90508, 1167200:90565, 1168000:90627, 1168800:90679, 1169600:90740, 1170400:90796, 1171200:90854, 1172000:90910, 1172800:90965, 1173600:91021, 1174400:91074, 1175200:91133, 1176000:91193, 1176800:91250, 1177600:91305, 1178400:91371, 1179200:91427, 1180000:91490, 1180800:91551, 1181600:91615, 1182400:91666, 1183200:91729, 1184000:91788, 1184800:91849, 1185600:91902, 1186400:91964, 1187200:92012, 1188000:92079, 1188800:92139, 1189600:92191, 1190400:92248, 1191200:92312, 1192000:92367, 1192800:92422, 1193600:92482, 1194400:92541, 1195200:92602, 1196000:92652, 1196800:92705, 1197600:92767, 1198400:92824, 1199200:92877, 1200000:92938, 1200800:92987, 1201600:93046, 1202400:93102, 1203200:93155, 1204000:93216, 1204800:93266, 1205600:93313, 1206400:93374, 1207200:93428, 1208000:93478, 1208800:93531, 1209600:93587, 1210400:93644, 1211200:93703, 1212000:93765, 1212800:93823, 1213600:93883, 1214400:93943, 1215200:94005, 1216000:94059, 1216800:94114, 1217600:94181, 1218400:94235, 1219200:94287, 1220000:94358, 1220800:94403, 1221600:94462, 1222400:94510, 1223200:94570, 1224000:94624, 1224800:94675, 1225600:94739, 1226400:94799, 1227200:94857, 1228000:94906, 1228800:94964, 1229600:95027, 1230400:95081, 1231200:95133, 1232000:95201, 1232800:95247, 1233600:95304, 1234400:95351, 1235200:95405, 1236000:95461, 1236800:95512, 1237600:95572, 1238400:95625, 1239200:95684, 1240000:95745, 1240800:95802, 1241600:95860, 1242400:95913, 1243200:95965, 1244000:96024, 1244800:96086, 1245600:96133, 1246400:96200, 1247200:96257, 1248000:96316, 1248800:96377, 1249600:96438, 1250400:96495, 1251200:96552, 1252000:96603, 1252800:96657, 1253600:96707, 1254400:96768, 1255200:96833, 1256000:96891, 1256800:96939, 1257600:97007, 1258400:97062, 1259200:97132, 1260000:97182, 1260800:97241, 1261600:97292, 1262400:97347, 1263200:97410, 1264000:97468, 1264800:97515, 1265600:97581, 1266400:97648, 1267200:97708, 1268000:97761, 1268800:97819, 1269600:97877, 1270400:97931, 1271200:97993, 1272000:98052, 1272800:98104, 1273600:98169, 1274400:98224, 1275200:98268, 1276000:98324, 1276800:98382, 1277600:98436, 1278400:98491, 1279200:98551, 1280000:98610, 1280800:98661, 1281600:98717, 1282400:98778, 1283200:98843, 1284000:98892, 1284800:98945, 1285600:99004, 1286400:99065, 1287200:99125, 1288000:99186, 1288800:99244, 1289600:99305, 1290400:99358, 1291200:99411, 1292000:99462, 1292800:99521, 1293600:99577, 1294400:99634, 1295200:99682, 1296000:99740, 1296800:99798, 1297600:99863, 1298400:99915, 1299200:99962, 1300000:100021, 1300800:100079, 1301600:100140, 1302400:100200, 1303200:100252, 1304000:100314, 1304800:100366, 1305600:100419, 1306400:100478, 1307200:100537, 1308000:100586, 1308800:100643, 1309600:100697, 1310400:100765, 1311200:100819, 1312000:100878, 1312800:100932, 1313600:100982, 1314400:101041, 1315200:101090, 1316000:101152, 1316800:101206, 1317600:101268, 1318400:101322, 1319200:101382, 1320000:101433, 1320800:101483, 1321600:101547, 1322400:101614, 1323200:101680, 1324000:101733, 1324800:101789, 1325600:101842, 1326400:101898, 1327200:101959, 1328000:102005, 1328800:102065, 1329600:102119, 1330400:102172, 1331200:102222, 1332000:102287, 1332800:102345, 1333600:102398, 1334400:102457, 1335200:102503, 1336000:102559, 1336800:102622, 1337600:102678, 1338400:102733, 1339200:102795, 1340000:102852, 1340800:102915, 1341600:102970, 1342400:103031, 1343200:103087, 1344000:103147, 1344800:103200, 1345600:103253, 1346400:103308, 1347200:103360, 1348000:103416, 1348800:103471, 1349600:103520, 1350400:103575, 1351200:103639, 1352000:103696, 1352800:103746, 1353600:103803, 1354400:103865, 1355200:103913, 1356000:103981, 1356800:104043, 1357600:104088, 1358400:104149, 1359200:104202, 1360000:104258, 1360800:104319, 1361600:104375, 1362400:104429, 1363200:104486, 1364000:104545, 1364800:104603, 1365600:104660, 1366400:104705, 1367200:104770, 1368000:104824, 1368800:104884, 1369600:104941, 1370400:104996, 1371200:105058, 1372000:105108, 1372800:105161, 1373600:105219, 1374400:105270, 1375200:105331, 1376000:105388, 1376800:105448, 1377600:105503, 1378400:105570, 1379200:105631, 1380000:105690, 1380800:105746, 1381600:105809, 1382400:105862, 1383200:105908, 1384000:105960, 1384800:106011, 1385600:106078, 1386400:106139, 1387200:106194, 1388000:106245, 1388800:106304, 1389600:106358, 1390400:106413, 1391200:106474, 1392000:106527, 1392800:106575, 1393600:106631, 1394400:106693, 1395200:106752, 1396000:106809, 1396800:106874, 1397600:106938, 1398400:107000, 1399200:107058, 1400000:107126, 1400800:107174, 1401600:107227, 1402400:107285, 1403200:107332, 1404000:107397, 1404800:107445, 1405600:107503, 1406400:107548, 1407200:107607, 1408000:107667, 1408800:107722, 1409600:107780, 1410400:107835, 1411200:107895, 1412000:107948, 1412800:108015, 1413600:108072, 1414400:108121, 1415200:108165, 1416000:108215, 1416800:108269, 1417600:108328, 1418400:108382, 1419200:108430, 1420000:108487, 1420800:108541, 1421600:108598, 1422400:108651, 1423200:108706, 1424000:108772, 1424800:108827, 1425600:108884, 1426400:108949, 1427200:109007, 1428000:109065, 1428800:109114, 1429600:109172, 1430400:109227, 1431200:109287, 1432000:109349, 1432800:109406, 1433600:109464, 1434400:109523, 1435200:109587, 1436000:109642, 1436800:109700, 1437600:109757, 1438400:109816, 1439200:109874, 1440000:109928, 1440800:109982, 1441600:110041, 1442400:110094, 1443200:110150, 1444000:110204, 1444800:110256, 1445600:110320, 1446400:110378, 1447200:110433, 1448000:110496, 1448800:110542, 1449600:110600, 1450400:110658, 1451200:110719, 1452000:110769, 1452800:110825, 1453600:110882, 1454400:110938, 1455200:111008, 1456000:111070, 1456800:111120, 1457600:111172, 1458400:111227, 1459200:111280, 1460000:111331, 1460800:111390, 1461600:111449, 1462400:111514, 1463200:111572, 1464000:111627, 1464800:111680, 1465600:111745, 1466400:111803, 1467200:111859, 1468000:111913, 1468800:111960, 1469600:112016, 1470400:112068, 1471200:112117, 1472000:112179, 1472800:112237, 1473600:112296, 1474400:112354, 1475200:112398, 1476000:112448, 1476800:112506, 1477600:112571, 1478400:112632, 1479200:112692, 1480000:112752, 1480800:112810, 1481600:112860, 1482400:112917, 1483200:112979, 1484000:113036, 1484800:113094, 1485600:113145, 1486400:113197, 1487200:113257, 1488000:113310, 1488800:113365, 1489600:113428, 1490400:113491, 1491200:113544, 1492000:113604, 1492800:113661, 1493600:113719, 1494400:113781, 1495200:113836, 1496000:113892, 1496800:113954, 1497600:114004, 1498400:114054, 1499200:114105, 1500000:114155, 1500800:114220, 1501600:114276, 1502400:114334, 1503200:114390, 1504000:114450, 1504800:114510, 1505600:114576, 1506400:114631, 1507200:114695, 1508000:114741, 1508800:114801, 1509600:114860, 1510400:114920, 1511200:114975, 1512000:115034, 1512800:115087, 1513600:115148, 1514400:115201, 1515200:115256, 1516000:115308, 1516800:115367, 1517600:115422, 1518400:115480, 1519200:115532, 1520000:115588, 1520800:115645, 1521600:115694, 1522400:115748, 1523200:115799, 1524000:115860, 1524800:115923, 1525600:115976, 1526400:116034, 1527200:116083, 1528000:116140, 1528800:116193, 1529600:116251, 1530400:116304, 1531200:116358, 1532000:116404, 1532800:116457, 1533600:116513, 1534400:116569, 1535200:116620, 1536000:116684, 1536800:116742, 1537600:116795, 1538400:116856, 1539200:116908, 1540000:116965, 1540800:117022, 1541600:117078, 1542400:117134, 1543200:117187, 1544000:117234, 1544800:117285, 1545600:117348, 1546400:117409, 1547200:117459, 1548000:117523, 1548800:117580, 1549600:117639, 1550400:117694, 1551200:117751, 1552000:117802, 1552800:117855, 1553600:117920, 1554400:117970, 1555200:118025, 1556000:118088, 1556800:118146, 1557600:118203, 1558400:118256, 1559200:118317, 1560000:118376, 1560800:118430, 1561600:118485, 1562400:118534, 1563200:118580, 1564000:118641, 1564800:118697, 1565600:118760, 1566400:118818, 1567200:118875, 1568000:118925, 1568800:118974, 1569600:119032, 1570400:119085, 1571200:119144, 1572000:119203, 1572800:119264, 1573600:119314, 1574400:119376, 1575200:119427, 1576000:119483, 1576800:119541, 1577600:119600, 1578400:119651, 1579200:119703, 1580000:119758, 1580800:119818, 1581600:119871, 1582400:119922, 1583200:119976, 1584000:120032, 1584800:120089, 1585600:120146, 1586400:120195, 1587200:120246, 1588000:120301, 1588800:120358, 1589600:120420, 1590400:120481, 1591200:120526, 1592000:120577, 1592800:120630, 1593600:120687, 1594400:120742, 1595200:120802, 1596000:120861, 1596800:120915, 1597600:120966, 1598400:121026, 1599200:121078, 1600000:121127, 1600800:121183, 1601600:121247, 1602400:121307, 1603200:121371, 1604000:121432, 1604800:121495, 1605600:121547, 1606400:121599, 1607200:121662, 1608000:121715, 1608800:121771, 1609600:121820, 1610400:121874, 1611200:121936, 1612000:121991, 1612800:122045, 1613600:122091, 1614400:122145, 1615200:122205, 1616000:122259, 1616800:122314, 1617600:122367, 1618400:122428, 1619200:122482, 1620000:122540, 1620800:122595, 1621600:122652, 1622400:122704, 1623200:122766, 1624000:122818, 1624800:122872, 1625600:122927, 1626400:122993, 1627200:123053, 1628000:123112, 1628800:123167, 1629600:123229, 1630400:123278, 1631200:123334, 1632000:123388, 1632800:123447, 1633600:123506, 1634400:123569, 1635200:123631, 1636000:123683, 1636800:123746, 1637600:123791, 1638400:123841, 1639200:123888, 1640000:123942, 1640800:123996, 1641600:124044, 1642400:124100, 1643200:124159, 1644000:124220, 1644800:124274, 1645600:124326, 1646400:124391, 1647200:124448, 1648000:124500, 1648800:124548, 1649600:124602, 1650400:124665, 1651200:124718, 1652000:124772, 1652800:124824, 1653600:124893, 1654400:124951, 1655200:125007, 1656000:125065, 1656800:125122, 1657600:125178, 1658400:125230, 1659200:125283, 1660000:125335, 1660800:125393, 1661600:125441, 1662400:125496, 1663200:125559, 1664000:125614, 1664800:125655, 1665600:125715, 1666400:125774, 1667200:125831, 1668000:125903, 1668800:125960, 1669600:126022, 1670400:126071, 1671200:126131, 1672000:126179, 1672800:126231, 1673600:126288, 1674400:126344, 1675200:126408, 1676000:126468, 1676800:126518, 1677600:126577, 1678400:126635, 1679200:126697, 1680000:126753, 1680800:126809, 1681600:126865, 1682400:126918, 1683200:126971, 1684000:127014, 1684800:127068, 1685600:127131, 1686400:127190, 1687200:127248, 1688000:127300, 1688800:127352, 1689600:127400, 1690400:127459, 1691200:127510, 1692000:127570, 1692800:127626, 1693600:127681, 1694400:127742, 1695200:127791, 1696000:127848, 1696800:127904, 1697600:127962, 1698400:128023, 1699200:128080, 1700000:128141, 1700800:128198, 1701600:128255, 1702400:128314, 1703200:128370, 1704000:128418, 1704800:128472, 1705600:128529, 1706400:128582, 1707200:128638, 1708000:128696, 1708800:128751, 1709600:128809, 1710400:128866, 1711200:128924, 1712000:128977, 1712800:129028, 1713600:129076, 1714400:129129, 1715200:129189, 1716000:129246, 1716800:129309, 1717600:129357, 1718400:129410, 1719200:129464, 1720000:129522, 1720800:129581, 1721600:129635, 1722400:129691, 1723200:129738, 1724000:129787, 1724800:129848, 1725600:129902, 1726400:129957, 1727200:130020, 1728000:130079, 1728800:130126, 1729600:130184, 1730400:130236, 1731200:130290, 1732000:130343, 1732800:130397, 1733600:130455, 1734400:130511, 1735200:130563, 1736000:130618, 1736800:130672, 1737600:130725, 1738400:130777, 1739200:130838, 1740000:130902, 1740800:130960, 1741600:131012, 1742400:131060, 1743200:131116, 1744000:131172, 1744800:131228, 1745600:131279, 1746400:131338, 1747200:131403, 1748000:131453, 1748800:131513, 1749600:131584, 1750400:131637, 1751200:131695, 1752000:131749, 1752800:131810, 1753600:131868, 1754400:131923, 1755200:131977, 1756000:132032, 1756800:132084, 1757600:132137, 1758400:132195, 1759200:132242, 1760000:132292, 1760800:132344, 1761600:132388, 1762400:132440, 1763200:132494, 1764000:132552, 1764800:132611, 1765600:132660, 1766400:132720, 1767200:132773, 1768000:132834, 1768800:132893, 1769600:132945, 1770400:132997, 1771200:133058, 1772000:133104, 1772800:133160, 1773600:133214, 1774400:133281, 1775200:133332, 1776000:133391, 1776800:133448, 1777600:133498, 1778400:133559, 1779200:133618, 1780000:133671, 1780800:133737, 1781600:133790, 1782400:133842, 1783200:133901, 1784000:133960, 1784800:134014, 1785600:134066, 1786400:134119, 1787200:134178, 1788000:134231, 1788800:134286, 1789600:134335, 1790400:134388, 1791200:134448, 1792000:134505, 1792800:134567, 1793600:134619, 1794400:134674, 1795200:134733, 1796000:134794, 1796800:134841, 1797600:134893, 1798400:134951, 1799200:135020, 1800000:135072, 1800800:135129, 1801600:135182, 1802400:135236, 1803200:135287, 1804000:135341, 1804800:135395, 1805600:135454, 1806400:135517, 1807200:135574, 1808000:135632, 1808800:135682, 1809600:135748, 1810400:135802, 1811200:135857, 1812000:135912, 1812800:135966, 1813600:136017, 1814400:136073, 1815200:136128, 1816000:136192, 1816800:136242, 1817600:136291, 1818400:136341, 1819200:136395, 1820000:136448, 1820800:136510, 1821600:136563, 1822400:136614, 1823200:136674, 1824000:136733, 1824800:136794, 1825600:136853, 1826400:136911, 1827200:136970, 1828000:137024, 1828800:137087, 1829600:137137, 1830400:137195, 1831200:137255, 1832000:137315, 1832800:137368, 1833600:137422, 1834400:137478, 1835200:137536, 1836000:137584, 1836800:137630, 1837600:137680, 1838400:137734, 1839200:137782, 1840000:137841, 1840800:137894, 1841600:137946, 1842400:138002, 1843200:138069, 1844000:138123, 1844800:138178, 1845600:138238, 1846400:138294, 1847200:138343, 1848000:138406, 1848800:138454, 1849600:138517, 1850400:138566, 1851200:138613, 1852000:138681, 1852800:138739, 1853600:138790, 1854400:138851, 1855200:138910, 1856000:138974, 1856800:139021, 1857600:139082, 1858400:139137, 1859200:139193, 1860000:139249, 1860800:139307, 1861600:139361, 1862400:139414, 1863200:139467, 1864000:139530, 1864800:139581, 1865600:139649, 1866400:139708, 1867200:139763, 1868000:139822, 1868800:139880, 1869600:139931, 1870400:139982, 1871200:140037, 1872000:140094, 1872800:140148, 1873600:140203, 1874400:140248, 1875200:140310, 1876000:140365, 1876800:140425, 1877600:140479, 1878400:140536, 1879200:140590, 1880000:140641, 1880800:140693, 1881600:140760, 1882400:140816, 1883200:140863, 1884000:140920, 1884800:140973, 1885600:141031, 1886400:141088, 1887200:141147, 1888000:141197, 1888800:141250, 1889600:141316, 1890400:141371, 1891200:141425, 1892000:141483, 1892800:141542, 1893600:141601, 1894400:141656, 1895200:141704, 1896000:141755, 1896800:141817, 1897600:141868, 1898400:141925, 1899200:141983, 1900000:142029, 1900800:142088, 1901600:142135, 1902400:142191, 1903200:142243, 1904000:142298, 1904800:142350, 1905600:142404, 1906400:142458, 1907200:142510, 1908000:142573, 1908800:142633, 1909600:142691, 1910400:142746, 1911200:142806, 1912000:142858, 1912800:142917, 1913600:142972, 1914400:143025, 1915200:143082, 1916000:143148, 1916800:143201, 1917600:143263, 1918400:143316, 1919200:143364, 1920000:143414, 1920800:143472, 1921600:143527, 1922400:143576, 1923200:143636, 1924000:143691, 1924800:143743, 1925600:143798, 1926400:143858, 1927200:143919, 1928000:143984, 1928800:144038, 1929600:144094, 1930400:144152, 1931200:144201, 1932000:144262, 1932800:144313, 1933600:144365, 1934400:144419, 1935200:144475, 1936000:144528, 1936800:144585, 1937600:144634, 1938400:144691, 1939200:144746, 1940000:144810, 1940800:144867, 1941600:144923, 1942400:144979, 1943200:145030, 1944000:145090, 1944800:145144, 1945600:145200, 1946400:145256, 1947200:145318, 1948000:145375, 1948800:145434, 1949600:145478, 1950400:145533, 1951200:145586, 1952000:145637, 1952800:145691, 1953600:145750, 1954400:145812, 1955200:145869, 1956000:145922, 1956800:145975, 1957600:146025, 1958400:146072, 1959200:146130, 1960000:146186, 1960800:146239, 1961600:146299, 1962400:146356, 1963200:146413, 1964000:146464, 1964800:146516, 1965600:146570, 1966400:146623, 1967200:146680, 1968000:146728, 1968800:146785, 1969600:146834, 1970400:146883, 1971200:146938, 1972000:146983, 1972800:147041, 1973600:147101, 1974400:147148, 1975200:147199, 1976000:147248, 1976800:147308, 1977600:147359, 1978400:147416, 1979200:147475, 1980000:147529, 1980800:147592, 1981600:147644, 1982400:147700, 1983200:147763, 1984000:147816, 1984800:147874, 1985600:147927, 1986400:147977, 1987200:148033, 1988000:148090, 1988800:148148, 1989600:148196, 1990400:148253, 1991200:148309, 1992000:148367, 1992800:148422, 1993600:148476, 1994400:148529, 1995200:148586, 1996000:148642, 1996800:148707, 1997600:148766, 1998400:148826, 1999200:148880, 2000000:148933, 2000800:148990, 2001600:149044, 2002400:149098, 2003200:149152, 2004000:149206, 2004800:149259, 2005600:149322, 2006400:149376, 2007200:149430, 2008000:149495, 2008800:149557, 2009600:149605, 2010400:149665, 2011200:149717, 2012000:149767, 2012800:149821, 2013600:149879, 2014400:149943, 2015200:150002, 2016000:150058, 2016800:150113, 2017600:150163, 2018400:150216, 2019200:150277, 2020000:150328, 2020800:150385, 2021600:150441, 2022400:150500, 2023200:150556, 2024000:150610, 2024800:150658, 2025600:150710, 2026400:150765, 2027200:150819, 2028000:150878, 2028800:150937, 2029600:150991, 2030400:151048, 2031200:151098, 2032000:151147, 2032800:151215, 2033600:151279, 2034400:151332, 2035200:151391, 2036000:151441, 2036800:151492, 2037600:151550, 2038400:151599, 2039200:151653, 2040000:151711, 2040800:151769, 2041600:151814, 2042400:151875, 2043200:151935, 2044000:151990, 2044800:152039, 2045600:152089, 2046400:152148, 2047200:152205, 2048000:152252, 2048800:152302, 2049600:152355, 2050400:152414, 2051200:152467, 2052000:152521, 2052800:152571, 2053600:152623, 2054400:152682, 2055200:152742, 2056000:152786, 2056800:152845, 2057600:152902, 2058400:152962, 2059200:153016, 2060000:153078, 2060800:153129, 2061600:153183, 2062400:153237, 2063200:153291, 2064000:153354, 2064800:153414, 2065600:153465, 2066400:153519, 2067200:153578, 2068000:153625, 2068800:153683, 2069600:153737, 2070400:153795, 2071200:153849, 2072000:153909, 2072800:153959, 2073600:154013, 2074400:154063, 2075200:154116, 2076000:154174, 2076800:154222, 2077600:154270, 2078400:154327, 2079200:154390, 2080000:154445, 2080800:154500, 2081600:154550, 2082400:154597, 2083200:154659, 2084000:154713, 2084800:154764, 2085600:154817, 2086400:154873, 2087200:154932, 2088000:154992, 2088800:155052, 2089600:155107, 2090400:155164, 2091200:155202, 2092000:155268, 2092800:155323, 2093600:155383, 2094400:155432, 2095200:155478, 2096000:155536, 2096800:155584, 2097600:155641, 2098400:155695, 2099200:155750, 2100000:155805, 2100800:155862, 2101600:155921, 2102400:155975, 2103200:156037, 2104000:156086, 2104800:156145, 2105600:156200, 2106400:156259, 2107200:156319, 2108000:156366, 2108800:156426, 2109600:156476, 2110400:156535, 2111200:156589, 2112000:156644, 2112800:156689, 2113600:156744, 2114400:156804, 2115200:156859, 2116000:156915, 2116800:156973, 2117600:157030, 2118400:157089, 2119200:157134, 2120000:157187, 2120800:157240, 2121600:157291, 2122400:157349, 2123200:157404, 2124000:157458, 2124800:157509, 2125600:157560, 2126400:157624, 2127200:157680, 2128000:157737, 2128800:157795, 2129600:157856, 2130400:157907, 2131200:157956, 2132000:158012, 2132800:158070, 2133600:158123, 2134400:158175, 2135200:158224, 2136000:158279, 2136800:158341, 2137600:158398, 2138400:158452, 2139200:158504, 2140000:158557, 2140800:158614, 2141600:158667, 2142400:158729, 2143200:158781, 2144000:158837, 2144800:158906, 2145600:158961, 2146400:159011, 2147200:159065, 2148000:159118, 2148800:159175, 2149600:159227, 2150400:159272, 2151200:159327, 2152000:159383, 2152800:159440, 2153600:159498, 2154400:159553, 2155200:159610, 2156000:159663, 2156800:159721, 2157600:159785, 2158400:159843, 2159200:159904, 2160000:159962, 2160800:160013, 2161600:160063, 2162400:160123, 2163200:160178, 2164000:160236, 2164800:160282, 2165600:160335, 2166400:160382, 2167200:160437, 2168000:160488, 2168800:160551, 2169600:160601, 2170400:160657, 2171200:160710, 2172000:160764, 2172800:160823, 2173600:160884, 2174400:160935, 2175200:160986, 2176000:161040, 2176800:161102, 2177600:161163, 2178400:161215, 2179200:161266, 2180000:161319, 2180800:161374, 2181600:161429, 2182400:161478, 2183200:161524, 2184000:161583, 2184800:161640, 2185600:161694, 2186400:161749, 2187200:161804, 2188000:161856, 2188800:161915, 2189600:161975, 2190400:162029, 2191200:162085, 2192000:162132, 2192800:162190, 2193600:162248, 2194400:162304, 2195200:162356, 2196000:162409, 2196800:162468, 2197600:162519, 2198400:162565, 2199200:162615, 2200000:162662, 2200800:162718, 2201600:162776, 2202400:162825, 2203200:162886, 2204000:162940, 2204800:162997, 2205600:163048, 2206400:163096, 2207200:163162, 2208000:163223, 2208800:163274, 2209600:163325, 2210400:163400, 2211200:163452, 2212000:163501, 2212800:163560, 2213600:163610, 2214400:163653, 2215200:163704, 2216000:163762, 2216800:163814, 2217600:163874, 2218400:163920, 2219200:163972, 2220000:164023, 2220800:164074, 2221600:164123, 2222400:164183, 2223200:164236, 2224000:164295, 2224800:164345, 2225600:164406, 2226400:164456, 2227200:164513, 2228000:164577, 2228800:164639, 2229600:164691, 2230400:164743, 2231200:164794, 2232000:164852, 2232800:164901, 2233600:164962, 2234400:165017, 2235200:165072, 2236000:165135, 2236800:165190, 2237600:165244, 2238400:165294, 2239200:165346, 2240000:165398, 2240800:165455, 2241600:165514, 2242400:165562, 2243200:165611, 2244000:165668, 2244800:165723, 2245600:165780, 2246400:165838, 2247200:165886, 2248000:165944, 2248800:166005, 2249600:166056, 2250400:166099, 2251200:166151, 2252000:166207, 2252800:166256, 2253600:166316, 2254400:166368, 2255200:166428, 2256000:166485, 2256800:166548, 2257600:166603, 2258400:166665, 2259200:166721, 2260000:166769, 2260800:166838, 2261600:166888, 2262400:166935, 2263200:166987, 2264000:167047, 2264800:167110, 2265600:167157, 2266400:167213, 2267200:167275, 2268000:167329, 2268800:167384, 2269600:167440, 2270400:167501, 2271200:167557, 2272000:167620, 2272800:167678, 2273600:167737, 2274400:167789, 2275200:167846, 2276000:167903, 2276800:167954, 2277600:168001, 2278400:168064, 2279200:168114, 2280000:168164, 2280800:168215, 2281600:168268, 2282400:168321, 2283200:168367, 2284000:168418, 2284800:168466, 2285600:168524, 2286400:168577, 2287200:168635, 2288000:168689, 2288800:168742, 2289600:168795, 2290400:168853, 2291200:168909, 2292000:168965, 2292800:169022, 2293600:169072, 2294400:169130, 2295200:169181, 2296000:169235, 2296800:169282, 2297600:169339, 2298400:169401, 2299200:169455, 2300000:169511, 2300800:169567, 2301600:169632, 2302400:169687, 2303200:169733, 2304000:169789, 2304800:169847, 2305600:169889, 2306400:169947, 2307200:169999, 2308000:170055, 2308800:170115, 2309600:170172, 2310400:170225, 2311200:170286, 2312000:170340, 2312800:170382, 2313600:170434, 2314400:170491, 2315200:170547, 2316000:170596, 2316800:170650, 2317600:170695, 2318400:170749, 2319200:170805, 2320000:170863, 2320800:170910, 2321600:170964, 2322400:171017, 2323200:171070, 2324000:171130, 2324800:171177, 2325600:171224, 2326400:171280, 2327200:171342, 2328000:171406, 2328800:171456, 2329600:171509, 2330400:171556, 2331200:171610, 2332000:171657, 2332800:171714, 2333600:171771, 2334400:171836, 2335200:171886, 2336000:171941, 2336800:171995, 2337600:172053, 2338400:172101, 2339200:172154, 2340000:172206, 2340800:172265, 2341600:172318, 2342400:172378, 2343200:172430, 2344000:172485, 2344800:172541, 2345600:172590, 2346400:172636, 2347200:172683, 2348000:172747, 2348800:172798, 2349600:172849, 2350400:172907, 2351200:172963, 2352000:173011, 2352800:173068, 2353600:173114, 2354400:173175, 2355200:173233, 2356000:173278, 2356800:173334, 2357600:173388, 2358400:173448, 2359200:173506, 2360000:173563, 2360800:173615, 2361600:173667, 2362400:173723, 2363200:173783, 2364000:173837, 2364800:173898, 2365600:173955, 2366400:174006, 2367200:174060, 2368000:174116, 2368800:174172, 2369600:174228, 2370400:174280, 2371200:174335, 2372000:174383, 2372800:174439, 2373600:174500, 2374400:174548, 2375200:174591, 2376000:174646, 2376800:174704, 2377600:174758, 2378400:174808, 2379200:174861, 2380000:174916, 2380800:174975, 2381600:175036, 2382400:175091, 2383200:175148, 2384000:175201, 2384800:175251, 2385600:175297, 2386400:175362, 2387200:175419, 2388000:175477, 2388800:175532, 2389600:175586, 2390400:175649, 2391200:175707, 2392000:175756, 2392800:175812, 2393600:175855, 2394400:175914, 2395200:175959, 2396000:176007, 2396800:176065, 2397600:176127, 2398400:176191, 2399200:176245, 2400000:176302, 2400800:176353, 2401600:176407, 2402400:176452, 2403200:176509, 2404000:176568, 2404800:176619, 2405600:176678, 2406400:176726, 2407200:176781, 2408000:176835, 2408800:176883, 2409600:176941, 2410400:176985, 2411200:177044, 2412000:177090, 2412800:177149, 2413600:177207, 2414400:177267, 2415200:177321, 2416000:177369, 2416800:177429, 2417600:177486, 2418400:177544, 2419200:177599, 2420000:177654, 2420800:177701, 2421600:177765, 2422400:177817, 2423200:177876, 2424000:177927, 2424800:177971, 2425600:178027, 2426400:178085, 2427200:178141, 2428000:178194, 2428800:178250, 2429600:178303, 2430400:178351, 2431200:178403, 2432000:178461, 2432800:178512, 2433600:178562, 2434400:178618, 2435200:178677, 2436000:178732, 2436800:178785, 2437600:178832, 2438400:178882, 2439200:178934, 2440000:178983, 2440800:179049, 2441600:179108, 2442400:179155, 2443200:179208, 2444000:179264, 2444800:179319, 2445600:179380, 2446400:179436, 2447200:179483, 2448000:179536, 2448800:179594, 2449600:179651, 2450400:179708, 2451200:179751, 2452000:179816, 2452800:179875, 2453600:179938, 2454400:179989, 2455200:180037, 2456000:180092, 2456800:180146, 2457600:180197, 2458400:180253, 2459200:180311, 2460000:180371, 2460800:180428, 2461600:180482, 2462400:180532, 2463200:180585, 2464000:180637, 2464800:180700, 2465600:180758, 2466400:180804, 2467200:180858, 2468000:180912, 2468800:180964, 2469600:181014, 2470400:181072, 2471200:181124, 2472000:181178, 2472800:181233, 2473600:181290, 2474400:181333, 2475200:181391, 2476000:181440, 2476800:181498, 2477600:181547, 2478400:181604, 2479200:181652, 2480000:181711, 2480800:181766, 2481600:181818, 2482400:181872, 2483200:181930, 2484000:181974, 2484800:182029, 2485600:182087, 2486400:182144, 2487200:182202, 2488000:182265, 2488800:182323, 2489600:182367, 2490400:182422, 2491200:182478, 2492000:182528, 2492800:182578, 2493600:182629, 2494400:182684, 2495200:182742, 2496000:182792, 2496800:182850, 2497600:182904, 2498400:182965, 2499200:183017, 2500000:183072, 2500800:183121, 2501600:183176, 2502400:183239, 2503200:183288, 2504000:183342, 2504800:183403, 2505600:183458, 2506400:183508, 2507200:183565, 2508000:183613, 2508800:183672, 2509600:183724, 2510400:183771, 2511200:183833, 2512000:183888, 2512800:183945, 2513600:184001, 2514400:184056, 2515200:184111, 2516000:184170, 2516800:184210, 2517600:184260, 2518400:184316, 2519200:184372, 2520000:184423, 2520800:184475, 2521600:184525, 2522400:184579, 2523200:184641, 2524000:184701, 2524800:184765, 2525600:184824, 2526400:184872, 2527200:184931, 2528000:184977, 2528800:185024, 2529600:185090, 2530400:185156, 2531200:185212, 2532000:185265, 2532800:185318, 2533600:185367, 2534400:185415, 2535200:185479, 2536000:185525, 2536800:185581, 2537600:185628, 2538400:185682, 2539200:185742, 2540000:185792, 2540800:185846, 2541600:185895, 2542400:185947, 2543200:185998, 2544000:186053, 2544800:186113, 2545600:186165, 2546400:186225, 2547200:186269, 2548000:186317, 2548800:186376, 2549600:186436, 2550400:186485, 2551200:186536, 2552000:186589, 2552800:186649, 2553600:186705, 2554400:186760, 2555200:186820, 2556000:186870, 2556800:186921, 2557600:186969, 2558400:187026, 2559200:187076, 2560000:187134, 2560800:187192, 2561600:187246, 2562400:187303, 2563200:187359, 2564000:187416, 2564800:187468, 2565600:187513, 2566400:187567, 2567200:187618, 2568000:187680, 2568800:187739, 2569600:187788, 2570400:187837, 2571200:187900, 2572000:187947, 2572800:188015, 2573600:188062, 2574400:188113, 2575200:188173, 2576000:188231, 2576800:188292, 2577600:188348, 2578400:188406, 2579200:188459, 2580000:188511, 2580800:188568, 2581600:188630, 2582400:188689, 2583200:188743, 2584000:188800, 2584800:188848, 2585600:188905, 2586400:188957, 2587200:189018, 2588000:189066, 2588800:189119, 2589600:189177, 2590400:189231, 2591200:189280, 2592000:189335, 2592800:189387, 2593600:189435, 2594400:189491, 2595200:189555, 2596000:189606, 2596800:189662, 2597600:189716, 2598400:189770, 2599200:189826, 2600000:189880, 2600800:189930, 2601600:189981, 2602400:190037, 2603200:190084, 2604000:190138, 2604800:190193, 2605600:190246, 2606400:190295, 2607200:190348, 2608000:190395, 2608800:190453, 2609600:190512, 2610400:190558, 2611200:190616, 2612000:190671, 2612800:190724, 2613600:190772, 2614400:190839, 2615200:190891, 2616000:190957, 2616800:191010, 2617600:191067, 2618400:191117, 2619200:191167, 2620000:191214, 2620800:191267, 2621600:191318, 2622400:191373, 2623200:191427, 2624000:191486, 2624800:191542, 2625600:191596, 2626400:191643, 2627200:191697, 2628000:191751, 2628800:191797, 2629600:191853, 2630400:191913, 2631200:191973, 2632000:192030, 2632800:192093, 2633600:192156, 2634400:192199, 2635200:192258, 2636000:192303, 2636800:192358, 2637600:192408, 2638400:192459, 2639200:192509, 2640000:192567, 2640800:192615, 2641600:192681, 2642400:192737, 2643200:192785, 2644000:192842, 2644800:192895, 2645600:192957, 2646400:193012, 2647200:193066, 2648000:193120, 2648800:193177, 2649600:193232, 2650400:193286, 2651200:193338, 2652000:193397, 2652800:193450, 2653600:193496, 2654400:193555, 2655200:193611, 2656000:193668, 2656800:193724, 2657600:193791, 2658400:193841, 2659200:193900, 2660000:193951, 2660800:194003, 2661600:194055, 2662400:194105, 2663200:194154, 2664000:194204, 2664800:194269, 2665600:194333, 2666400:194383, 2667200:194432, 2668000:194482, 2668800:194537, 2669600:194591, 2670400:194631, 2671200:194682, 2672000:194736, 2672800:194787, 2673600:194838, 2674400:194896, 2675200:194952, 2676000:195007, 2676800:195065, 2677600:195113, 2678400:195167, 2679200:195214, 2680000:195278, 2680800:195329, 2681600:195386, 2682400:195442, 2683200:195491, 2684000:195545, 2684800:195598, 2685600:195658, 2686400:195710, 2687200:195764, 2688000:195822, 2688800:195871, 2689600:195930, 2690400:195992, 2691200:196046, 2692000:196095, 2692800:196150, 2693600:196204, 2694400:196261, 2695200:196317, 2696000:196369, 2696800:196424, 2697600:196479, 2698400:196539, 2699200:196591, 2700000:196645, 2700800:196701, 2701600:196754, 2702400:196807, 2703200:196854, 2704000:196905, 2704800:196958, 2705600:197023, 2706400:197079, 2707200:197132, 2708000:197188, 2708800:197244, 2709600:197297, 2710400:197353, 2711200:197405, 2712000:197453, 2712800:197515, 2713600:197568, 2714400:197624, 2715200:197672, 2716000:197734, 2716800:197786, 2717600:197845, 2718400:197904, 2719200:197967, 2720000:198019, 2720800:198066, 2721600:198118, 2722400:198164, 2723200:198218, 2724000:198279, 2724800:198331, 2725600:198376, 2726400:198427, 2727200:198479, 2728000:198525, 2728800:198578, 2729600:198642, 2730400:198685, 2731200:198745, 2732000:198802, 2732800:198856, 2733600:198907, 2734400:198961, 2735200:199007, 2736000:199056, 2736800:199104, 2737600:199154, 2738400:199214, 2739200:199260, 2740000:199321, 2740800:199377, 2741600:199431, 2742400:199490, 2743200:199553, 2744000:199600, 2744800:199660, 2745600:199707, 2746400:199755, 2747200:199809, 2748000:199871, 2748800:199920, 2749600:199971, 2750400:200020, 2751200:200074, 2752000:200131, 2752800:200187, 2753600:200241, 2754400:200285, 2755200:200337, 2756000:200387, 2756800:200452, 2757600:200502, 2758400:200554, 2759200:200606, 2760000:200664, 2760800:200719, 2761600:200780, 2762400:200835, 2763200:200890, 2764000:200946, 2764800:200994, 2765600:201052, 2766400:201106, 2767200:201160, 2768000:201214, 2768800:201272, 2769600:201330, 2770400:201370, 2771200:201427, 2772000:201484, 2772800:201534, 2773600:201590, 2774400:201646, 2775200:201702, 2776000:201754, 2776800:201798, 2777600:201857, 2778400:201914, 2779200:201960, 2780000:202015, 2780800:202066, 2781600:202122, 2782400:202177, 2783200:202226, 2784000:202281, 2784800:202341, 2785600:202397, 2786400:202449, 2787200:202505, 2788000:202559, 2788800:202605, 2789600:202656, 2790400:202705, 2791200:202756, 2792000:202815, 2792800:202870, 2793600:202925, 2794400:202979, 2795200:203027, 2796000:203084, 2796800:203129, 2797600:203186, 2798400:203239, 2799200:203301, 2800000:203362, 2800800:203414, 2801600:203467, 2802400:203520, 2803200:203580, 2804000:203637, 2804800:203693, 2805600:203748, 2806400:203806, 2807200:203856, 2808000:203899, 2808800:203963, 2809600:204021, 2810400:204084, 2811200:204139, 2812000:204196, 2812800:204252, 2813600:204314, 2814400:204366, 2815200:204420, 2816000:204471, 2816800:204521, 2817600:204583, 2818400:204635, 2819200:204689, 2820000:204747, 2820800:204804, 2821600:204859, 2822400:204915, 2823200:204972, 2824000:205028, 2824800:205083, 2825600:205135, 2826400:205185, 2827200:205228, 2828000:205276, 2828800:205325, 2829600:205386, 2830400:205443, 2831200:205494, 2832000:205551, 2832800:205605, 2833600:205670, 2834400:205728, 2835200:205786, 2836000:205839, 2836800:205898, 2837600:205956, 2838400:206012, 2839200:206064, 2840000:206118, 2840800:206171, 2841600:206223, 2842400:206273, 2843200:206335, 2844000:206389, 2844800:206437, 2845600:206485, 2846400:206533, 2847200:206589, 2848000:206645, 2848800:206709, 2849600:206754, 2850400:206818, 2851200:206869, 2852000:206924, 2852800:206970, 2853600:207022, 2854400:207085, 2855200:207139, 2856000:207192, 2856800:207233, 2857600:207290, 2858400:207343, 2859200:207394, 2860000:207443, 2860800:207499, 2861600:207555, 2862400:207605, 2863200:207659, 2864000:207713, 2864800:207770, 2865600:207823, 2866400:207881, 2867200:207937, 2868000:207993, 2868800:208046, 2869600:208089, 2870400:208136, 2871200:208196, 2872000:208244, 2872800:208302, 2873600:208360, 2874400:208413, 2875200:208466, 2876000:208511, 2876800:208563, 2877600:208617, 2878400:208667, 2879200:208720, 2880000:208769, 2880800:208823, 2881600:208883, 2882400:208937, 2883200:208991, 2884000:209037, 2884800:209099, 2885600:209151, 2886400:209204, 2887200:209259, 2888000:209312, 2888800:209367, 2889600:209423, 2890400:209474, 2891200:209528, 2892000:209578, 2892800:209626, 2893600:209686, 2894400:209733, 2895200:209793, 2896000:209838, 2896800:209896, 2897600:209947, 2898400:209992, 2899200:210050, 2900000:210109, 2900800:210163, 2901600:210222, 2902400:210270, 2903200:210325, 2904000:210374, 2904800:210433, 2905600:210488, 2906400:210540, 2907200:210594, 2908000:210652, 2908800:210706, 2909600:210765, 2910400:210816, 2911200:210867, 2912000:210918, 2912800:210968, 2913600:211025, 2914400:211077, 2915200:211123, 2916000:211178, 2916800:211235, 2917600:211286, 2918400:211340, 2919200:211401, 2920000:211453, 2920800:211512, 2921600:211563, 2922400:211618, 2923200:211680, 2924000:211725, 2924800:211779, 2925600:211835, 2926400:211893, 2927200:211945, 2928000:211989, 2928800:212039, 2929600:212091, 2930400:212151, 2931200:212209, 2932000:212255, 2932800:212310, 2933600:212355, 2934400:212407, 2935200:212464, 2936000:212520, 2936800:212577, 2937600:212637, 2938400:212696, 2939200:212752, 2940000:212804, 2940800:212856, 2941600:212901, 2942400:212951, 2943200:212995, 2944000:213049, 2944800:213107, 2945600:213160, 2946400:213214, 2947200:213264, 2948000:213311, 2948800:213366, 2949600:213427, 2950400:213477, 2951200:213537, 2952000:213595, 2952800:213654, 2953600:213696, 2954400:213745, 2955200:213801, 2956000:213856, 2956800:213901, 2957600:213947, 2958400:214000, 2959200:214050, 2960000:214105, 2960800:214168, 2961600:214216, 2962400:214277, 2963200:214330, 2964000:214387, 2964800:214438, 2965600:214499, 2966400:214549, 2967200:214603, 2968000:214661, 2968800:214718, 2969600:214770, 2970400:214828, 2971200:214881, 2972000:214926, 2972800:214978, 2973600:215038, 2974400:215079, 2975200:215140, 2976000:215194, 2976800:215250, 2977600:215295, 2978400:215350, 2979200:215401, 2980000:215458, 2980800:215514, 2981600:215578, 2982400:215626, 2983200:215686, 2984000:215740, 2984800:215795, 2985600:215852, 2986400:215905, 2987200:215961, 2988000:216009, 2988800:216063, 2989600:216112, 2990400:216154, 2991200:216211, 2992000:216265, 2992800:216323, 2993600:216377, 2994400:216428, 2995200:216485, 2996000:216536, 2996800:216592, 2997600:216645, 2998400:216714, 2999200:216763, 3000000:216816, 3000800:216864, 3001600:216920, 3002400:216970, 3003200:217032, 3004000:217091, 3004800:217142, 3005600:217199, 3006400:217246, 3007200:217298, 3008000:217354, 3008800:217407, 3009600:217458, 3010400:217509, 3011200:217568, 3012000:217626, 3012800:217684, 3013600:217736, 3014400:217790, 3015200:217841, 3016000:217890, 3016800:217941, 3017600:217994, 3018400:218045, 3019200:218090, 3020000:218145, 3020800:218202, 3021600:218256, 3022400:218312, 3023200:218358, 3024000:218412, 3024800:218459, 3025600:218517, 3026400:218572, 3027200:218631, 3028000:218680, 3028800:218740, 3029600:218785, 3030400:218841, 3031200:218894, 3032000:218943, 3032800:218998, 3033600:219052, 3034400:219104, 3035200:219160, 3036000:219207, 3036800:219253, 3037600:219305, 3038400:219371, 3039200:219420, 3040000:219465, 3040800:219521, 3041600:219573, 3042400:219630, 3043200:219687, 3044000:219746, 3044800:219798, 3045600:219848, 3046400:219896, 3047200:219953, 3048000:220011, 3048800:220060, 3049600:220107, 3050400:220164, 3051200:220216, 3052000:220263, 3052800:220321, 3053600:220378, 3054400:220430, 3055200:220477, 3056000:220530, 3056800:220585, 3057600:220633, 3058400:220684, 3059200:220747, 3060000:220793, 3060800:220849, 3061600:220909, 3062400:220966, 3063200:221016, 3064000:221061, 3064800:221107, 3065600:221152, 3066400:221208, 3067200:221261, 3068000:221318, 3068800:221370, 3069600:221430, 3070400:221487, 3071200:221543, 3072000:221603, 3072800:221654, 3073600:221699, 3074400:221767, 3075200:221828, 3076000:221880, 3076800:221938, 3077600:221994, 3078400:222043, 3079200:222100, 3080000:222152, 3080800:222205, 3081600:222267, 3082400:222317, 3083200:222368, 3084000:222417, 3084800:222470, 3085600:222528, 3086400:222582, 3087200:222633, 3088000:222695, 3088800:222751, 3089600:222812, 3090400:222867, 3091200:222916, 3092000:222977, 3092800:223031, 3093600:223082, 3094400:223134, 3095200:223178, 3096000:223238, 3096800:223298, 3097600:223345, 3098400:223391, 3099200:223444, 3100000:223492, 3100800:223533, 3101600:223585, 3102400:223642, 3103200:223705, 3104000:223757, 3104800:223813, 3105600:223866, 3106400:223925, 3107200:223974, 3108000:224029, 3108800:224088, 3109600:224137, 3110400:224194, 3111200:224250, 3112000:224297, 3112800:224348, 3113600:224400, 3114400:224455, 3115200:224510, 3116000:224566, 3116800:224622, 3117600:224677, 3118400:224731, 3119200:224798, 3120000:224845, 3120800:224899, 3121600:224954, 3122400:225003, 3123200:225060, 3124000:225115, 3124800:225162, 3125600:225211, 3126400:225265, 3127200:225316, 3128000:225377, 3128800:225427, 3129600:225478, 3130400:225537, 3131200:225593, 3132000:225651, 3132800:225698, 3133600:225751, 3134400:225808, 3135200:225859, 3136000:225909, 3136800:225964, 3137600:226012, 3138400:226060, 3139200:226113, 3140000:226177, 3140800:226223, 3141600:226277, 3142400:226325, 3143200:226390, 3144000:226428, 3144800:226484, 3145600:226539, 3146400:226592, 3147200:226646, 3148000:226697, 3148800:226755, 3149600:226803, 3150400:226863, 3151200:226914, 3152000:226972, 3152800:227030, 3153600:227086, 3154400:227149, 3155200:227194, 3156000:227247, 3156800:227309, 3157600:227367, 3158400:227412, 3159200:227458, 3160000:227512, 3160800:227564, 3161600:227614, 3162400:227654, 3163200:227707, 3164000:227770, 3164800:227821, 3165600:227885, 3166400:227947, 3167200:228002, 3168000:228056, 3168800:228097, 3169600:228153, 3170400:228209, 3171200:228262, 3172000:228322, 3172800:228379, 3173600:228435, 3174400:228487, 3175200:228543, 3176000:228588, 3176800:228635, 3177600:228689, 3178400:228747, 3179200:228797, 3180000:228843, 3180800:228897, 3181600:228947, 3182400:229005, 3183200:229066, 3184000:229128, 3184800:229175, 3185600:229228, 3186400:229283, 3187200:229338, 3188000:229392, 3188800:229443, 3189600:229508, 3190400:229562, 3191200:229608, 3192000:229664, 3192800:229719, 3193600:229775, 3194400:229828, 3195200:229881, 3196000:229931, 3196800:229988, 3197600:230041, 3198400:230097, 3199200:230157, 3200000:230209, 3200800:230271, 3201600:230324, 3202400:230391, 3203200:230444, 3204000:230499, 3204800:230544, 3205600:230591, 3206400:230645, 3207200:230708, 3208000:230764, 3208800:230813, 3209600:230872, 3210400:230928, 3211200:230982, 3212000:231040, 3212800:231091, 3213600:231136, 3214400:231188, 3215200:231247, 3216000:231301, 3216800:231363, 3217600:231413, 3218400:231470, 3219200:231521, 3220000:231569, 3220800:231626, 3221600:231683, 3222400:231734, 3223200:231784, 3224000:231840, 3224800:231893, 3225600:231947, 3226400:231997, 3227200:232047, 3228000:232108, 3228800:232159, 3229600:232219, 3230400:232267, 3231200:232318, 3232000:232372, 3232800:232429, 3233600:232484, 3234400:232540, 3235200:232590, 3236000:232648, 3236800:232711, 3237600:232764, 3238400:232821, 3239200:232877, 3240000:232928, 3240800:232980, 3241600:233025, 3242400:233079, 3243200:233130, 3244000:233179, 3244800:233232, 3245600:233285, 3246400:233338, 3247200:233394, 3248000:233451, 3248800:233501, 3249600:233551, 3250400:233602, 3251200:233659, 3252000:233714, 3252800:233765, 3253600:233817, 3254400:233868, 3255200:233914, 3256000:233975, 3256800:234025, 3257600:234078, 3258400:234133, 3259200:234186, 3260000:234239, 3260800:234302, 3261600:234359, 3262400:234408, 3263200:234460, 3264000:234512, 3264800:234560, 3265600:234616, 3266400:234679, 3267200:234733, 3268000:234783, 3268800:234838, 3269600:234887, 3270400:234940, 3271200:234995, 3272000:235042, 3272800:235097, 3273600:235147, 3274400:235205, 3275200:235256, 3276000:235316, 3276800:235370, 3277600:235429, 3278400:235494, 3279200:235544, 3280000:235582, 3280800:235640, 3281600:235695, 3282400:235732, 3283200:235794, 3284000:235855, 3284800:235902, 3285600:235953, 3286400:236003, 3287200:236064, 3288000:236116, 3288800:236169, 3289600:236223, 3290400:236284, 3291200:236333, 3292000:236394, 3292800:236446, 3293600:236489, 3294400:236539, 3295200:236589, 3296000:236643, 3296800:236700, 3297600:236757, 3298400:236807, 3299200:236858, 3300000:236900, 3300800:236949, 3301600:237000, 3302400:237057, 3303200:237102, 3304000:237155, 3304800:237206, 3305600:237269, 3306400:237322, 3307200:237376, 3308000:237428, 3308800:237484, 3309600:237546, 3310400:237598, 3311200:237651, 3312000:237709, 3312800:237761, 3313600:237812, 3314400:237866, 3315200:237921, 3316000:237973, 3316800:238029, 3317600:238082, 3318400:238132, 3319200:238181, 3320000:238233, 3320800:238282, 3321600:238334, 3322400:238396, 3323200:238452, 3324000:238491, 3324800:238557, 3325600:238610, 3326400:238667, 3327200:238717, 3328000:238769, 3328800:238824, 3329600:238880, 3330400:238930, 3331200:238987, 3332000:239032, 3332800:239079, 3333600:239136, 3334400:239188, 3335200:239234, 3336000:239290, 3336800:239337, 3337600:239392, 3338400:239444, 3339200:239502, 3340000:239555, 3340800:239608, 3341600:239673, 3342400:239728, 3343200:239782, 3344000:239834, 3344800:239887, 3345600:239936, 3346400:239985, 3347200:240033, 3348000:240092, 3348800:240145, 3349600:240201, 3350400:240254, 3351200:240310, 3352000:240358, 3352800:240401, 3353600:240461, 3354400:240509, 3355200:240562, 3356000:240614, 3356800:240662, 3357600:240712, 3358400:240759, 3359200:240802, 3360000:240853, 3360800:240911, 3361600:240962, 3362400:241012, 3363200:241057, 3364000:241109, 3364800:241171, 3365600:241229, 3366400:241292, 3367200:241347, 3368000:241403, 3368800:241456, 3369600:241513, 3370400:241570, 3371200:241624, 3372000:241673, 3372800:241728, 3373600:241774, 3374400:241821, 3375200:241880, 3376000:241930, 3376800:241984, 3377600:242048, 3378400:242108, 3379200:242159, 3380000:242208, 3380800:242256, 3381600:242310, 3382400:242367, 3383200:242413, 3384000:242469, 3384800:242522, 3385600:242578, 3386400:242631, 3387200:242690, 3388000:242751, 3388800:242798, 3389600:242853, 3390400:242907, 3391200:242962, 3392000:243014, 3392800:243053, 3393600:243109, 3394400:243161, 3395200:243220, 3396000:243274, 3396800:243331, 3397600:243385, 3398400:243440, 3399200:243486, 3400000:243539, 3400800:243588, 3401600:243645, 3402400:243705, 3403200:243766, 3404000:243821, 3404800:243881, 3405600:243921, 3406400:243975, 3407200:244030, 3408000:244077, 3408800:244132, 3409600:244194, 3410400:244242, 3411200:244302, 3412000:244361, 3412800:244417, 3413600:244469, 3414400:244529, 3415200:244573, 3416000:244623, 3416800:244677, 3417600:244729, 3418400:244788, 3419200:244835, 3420000:244882, 3420800:244946, 3421600:244988, 3422400:245045, 3423200:245092, 3424000:245146, 3424800:245208, 3425600:245258, 3426400:245312, 3427200:245369, 3428000:245426, 3428800:245474, 3429600:245527, 3430400:245575, 3431200:245627, 3432000:245684, 3432800:245740, 3433600:245801, 3434400:245853, 3435200:245896, 3436000:245953, 3436800:246014, 3437600:246073, 3438400:246132, 3439200:246179, 3440000:246239, 3440800:246286, 3441600:246341, 3442400:246398, 3443200:246453, 3444000:246509, 3444800:246566, 3445600:246623, 3446400:246673, 3447200:246715, 3448000:246770, 3448800:246823, 3449600:246882, 3450400:246943, 3451200:246997, 3452000:247044, 3452800:247086, 3453600:247136, 3454400:247190, 3455200:247247, 3456000:247302, 3456800:247353, 3457600:247407, 3458400:247458, 3459200:247510, 3460000:247555, 3460800:247608, 3461600:247659, 3462400:247713, 3463200:247761, 3464000:247810, 3464800:247857, 3465600:247910, 3466400:247968, 3467200:248016, 3468000:248073, 3468800:248133, 3469600:248183, 3470400:248237, 3471200:248277, 3472000:248335, 3472800:248386, 3473600:248437, 3474400:248498, 3475200:248548, 3476000:248596, 3476800:248639, 3477600:248693, 3478400:248744, 3479200:248795, 3480000:248846, 3480800:248899, 3481600:248956, 3482400:249004, 3483200:249044, 3484000:249100, 3484800:249154, 3485600:249199, 3486400:249254, 3487200:249307, 3488000:249354, 3488800:249404, 3489600:249457, 3490400:249506, 3491200:249565, 3492000:249620, 3492800:249675, 3493600:249734, 3494400:249783, 3495200:249840, 3496000:249887, 3496800:249940, 3497600:249988, 3498400:250036, 3499200:250089, 3500000:250150, 3500800:250194, 3501600:250236, 3502400:250293, 3503200:250345, 3504000:250411, 3504800:250467, 3505600:250521, 3506400:250577, 3507200:250614, 3508000:250669, 3508800:250721, 3509600:250773, 3510400:250819, 3511200:250876, 3512000:250936, 3512800:250995, 3513600:251053, 3514400:251101, 3515200:251158, 3516000:251207, 3516800:251253, 3517600:251304, 3518400:251354, 3519200:251402, 3520000:251464, 3520800:251514, 3521600:251568, 3522400:251618, 3523200:251668, 3524000:251713, 3524800:251770, 3525600:251821, 3526400:251871, 3527200:251909, 3528000:251964, 3528800:252023, 3529600:252068, 3530400:252121, 3531200:252178, 3532000:252231, 3532800:252290, 3533600:252341, 3534400:252395, 3535200:252450, 3536000:252511, 3536800:252557, 3537600:252605, 3538400:252660, 3539200:252702, 3540000:252757, 3540800:252811, 3541600:252854, 3542400:252910, 3543200:252961, 3544000:253015, 3544800:253061, 3545600:253121, 3546400:253175, 3547200:253230, 3548000:253290, 3548800:253340, 3549600:253386, 3550400:253435, 3551200:253487, 3552000:253541, 3552800:253590, 3553600:253648, 3554400:253691, 3555200:253756, 3556000:253805, 3556800:253866, 3557600:253915, 3558400:253966, 3559200:254020, 3560000:254080, 3560800:254132, 3561600:254180, 3562400:254226, 3563200:254285, 3564000:254340, 3564800:254394, 3565600:254453, 3566400:254505, 3567200:254552, 3568000:254617, 3568800:254668, 3569600:254721, 3570400:254776, 3571200:254832, 3572000:254884, 3572800:254928, 3573600:254979, 3574400:255031, 3575200:255082, 3576000:255136, 3576800:255190, 3577600:255241, 3578400:255293, 3579200:255345, 3580000:255390, 3580800:255445, 3581600:255495, 3582400:255550, 3583200:255607, 3584000:255659, 3584800:255715, 3585600:255763, 3586400:255817, 3587200:255877, 3588000:255937, 3588800:255987, 3589600:256032, 3590400:256090, 3591200:256147, 3592000:256189, 3592800:256232, 3593600:256288, 3594400:256340, 3595200:256402, 3596000:256451, 3596800:256508, 3597600:256571, 3598400:256620, 3599200:256677, 3600000:256726, 3600800:256786, 3601600:256842, 3602400:256891, 3603200:256942, 3604000:256990, 3604800:257050, 3605600:257100, 3606400:257157, 3607200:257217, 3608000:257279, 3608800:257327, 3609600:257386, 3610400:257447, 3611200:257494, 3612000:257545, 3612800:257610, 3613600:257660, 3614400:257721, 3615200:257772, 3616000:257823, 3616800:257875, 3617600:257935, 3618400:257992, 3619200:258040, 3620000:258088, 3620800:258138, 3621600:258198, 3622400:258256, 3623200:258316, 3624000:258369, 3624800:258428, 3625600:258475, 3626400:258530, 3627200:258585, 3628000:258636, 3628800:258689, 3629600:258749, 3630400:258803, 3631200:258855, 3632000:258905, 3632800:258959, 3633600:259017, 3634400:259066, 3635200:259115, 3636000:259165, 3636800:259219, 3637600:259262, 3638400:259318, 3639200:259369, 3640000:259426, 3640800:259474, 3641600:259533, 3642400:259585, 3643200:259632, 3644000:259689, 3644800:259735, 3645600:259787, 3646400:259842, 3647200:259893, 3648000:259943, 3648800:259992, 3649600:260041, 3650400:260089, 3651200:260141, 3652000:260181, 3652800:260233, 3653600:260284, 3654400:260331, 3655200:260383, 3656000:260444, 3656800:260502, 3657600:260559, 3658400:260615, 3659200:260662, 3660000:260714, 3660800:260765, 3661600:260814, 3662400:260858, 3663200:260925, 3664000:260975, 3664800:261029, 3665600:261089, 3666400:261140, 3667200:261191, 3668000:261239, 3668800:261285, 3669600:261350, 3670400:261401, 3671200:261456, 3672000:261507, 3672800:261569, 3673600:261624, 3674400:261673, 3675200:261725, 3676000:261781, 3676800:261840, 3677600:261900, 3678400:261960, 3679200:262023, 3680000:262078, 3680800:262123, 3681600:262173, 3682400:262219, 3683200:262273, 3684000:262320, 3684800:262378, 3685600:262428, 3686400:262479, 3687200:262535, 3688000:262584, 3688800:262643, 3689600:262692, 3690400:262742, 3691200:262802, 3692000:262856, 3692800:262908, 3693600:262951, 3694400:263009, 3695200:263069, 3696000:263125, 3696800:263182, 3697600:263236, 3698400:263287, 3699200:263343, 3700000:263397, 3700800:263446, 3701600:263504, 3702400:263560, 3703200:263611, 3704000:263663, 3704800:263719, 3705600:263771, 3706400:263822, 3707200:263864, 3708000:263921, 3708800:263975, 3709600:264029, 3710400:264067, 3711200:264118, 3712000:264177, 3712800:264238, 3713600:264293, 3714400:264342, 3715200:264396, 3716000:264449, 3716800:264499, 3717600:264557, 3718400:264609, 3719200:264663, 3720000:264723, 3720800:264772, 3721600:264827, 3722400:264882, 3723200:264929, 3724000:264979, 3724800:265038, 3725600:265096, 3726400:265150, 3727200:265217, 3728000:265265, 3728800:265319, 3729600:265382, 3730400:265436, 3731200:265491, 3732000:265548, 3732800:265600, 3733600:265651, 3734400:265696, 3735200:265746, 3736000:265806, 3736800:265861, 3737600:265914, 3738400:265968, 3739200:266019, 3740000:266068, 3740800:266113, 3741600:266166, 3742400:266223, 3743200:266268, 3744000:266321, 3744800:266371, 3745600:266421, 3746400:266476, 3747200:266526, 3748000:266571, 3748800:266632, 3749600:266691, 3750400:266747, 3751200:266798, 3752000:266856, 3752800:266912, 3753600:266965, 3754400:267026, 3755200:267073, 3756000:267118, 3756800:267179, 3757600:267231, 3758400:267283, 3759200:267333, 3760000:267384, 3760800:267431, 3761600:267471, 3762400:267522, 3763200:267565, 3764000:267622, 3764800:267671, 3765600:267728, 3766400:267776, 3767200:267831, 3768000:267889, 3768800:267937, 3769600:267989, 3770400:268043, 3771200:268093, 3772000:268138, 3772800:268187, 3773600:268242, 3774400:268293, 3775200:268353, 3776000:268406, 3776800:268455, 3777600:268514, 3778400:268565, 3779200:268615, 3780000:268671, 3780800:268726, 3781600:268774, 3782400:268828, 3783200:268881, 3784000:268930, 3784800:268992, 3785600:269042, 3786400:269099, 3787200:269151, 3788000:269206, 3788800:269254, 3789600:269303, 3790400:269347, 3791200:269403, 3792000:269457, 3792800:269513, 3793600:269564, 3794400:269613, 3795200:269656, 3796000:269708, 3796800:269765, 3797600:269817, 3798400:269875, 3799200:269938, 3800000:269987, 3800800:270039, 3801600:270095, 3802400:270144, 3803200:270194, 3804000:270246, 3804800:270311, 3805600:270364, 3806400:270415, 3807200:270462, 3808000:270514, 3808800:270556, 3809600:270610, 3810400:270673, 3811200:270734, 3812000:270781, 3812800:270838, 3813600:270888, 3814400:270938, 3815200:270999, 3816000:271058, 3816800:271113, 3817600:271166, 3818400:271227, 3819200:271277, 3820000:271325, 3820800:271382, 3821600:271435, 3822400:271496, 3823200:271551, 3824000:271606, 3824800:271653, 3825600:271711, 3826400:271757, 3827200:271798, 3828000:271853, 3828800:271912, 3829600:271965, 3830400:272028, 3831200:272082, 3832000:272128, 3832800:272180, 3833600:272231, 3834400:272276, 3835200:272326, 3836000:272385, 3836800:272429, 3837600:272490, 3838400:272541, 3839200:272589, 3840000:272645, 3840800:272701, 3841600:272759, 3842400:272815, 3843200:272873, 3844000:272919, 3844800:272966, 3845600:273030, 3846400:273082, 3847200:273131, 3848000:273181, 3848800:273239, 3849600:273298, 3850400:273347, 3851200:273394, 3852000:273443, 3852800:273499, 3853600:273547, 3854400:273603, 3855200:273655, 3856000:273703, 3856800:273758, 3857600:273812, 3858400:273861, 3859200:273923, 3860000:273972, 3860800:274023, 3861600:274077, 3862400:274132, 3863200:274176, 3864000:274232, 3864800:274287, 3865600:274338, 3866400:274384, 3867200:274435, 3868000:274491, 3868800:274546, 3869600:274591, 3870400:274640, 3871200:274698, 3872000:274746, 3872800:274792, 3873600:274846, 3874400:274905, 3875200:274958, 3876000:275011, 3876800:275060, 3877600:275106, 3878400:275162, 3879200:275215, 3880000:275269, 3880800:275323, 3881600:275380, 3882400:275425, 3883200:275483, 3884000:275536, 3884800:275580, 3885600:275632, 3886400:275692, 3887200:275747, 3888000:275805, 3888800:275850, 3889600:275903, 3890400:275963, 3891200:276012, 3892000:276070, 3892800:276121, 3893600:276186, 3894400:276249, 3895200:276298, 3896000:276348, 3896800:276401, 3897600:276451, 3898400:276502, 3899200:276554, 3900000:276611, 3900800:276654, 3901600:276709, 3902400:276758, 3903200:276803, 3904000:276859, 3904800:276906, 3905600:276959, 3906400:277004, 3907200:277070, 3908000:277127, 3908800:277184, 3909600:277235, 3910400:277299, 3911200:277350, 3912000:277401, 3912800:277445, 3913600:277497, 3914400:277548, 3915200:277601, 3916000:277657, 3916800:277709, 3917600:277757, 3918400:277806, 3919200:277857, 3920000:277920, 3920800:277971, 3921600:278018, 3922400:278071, 3923200:278125, 3924000:278178, 3924800:278239, 3925600:278291, 3926400:278342, 3927200:278399, 3928000:278453, 3928800:278507, 3929600:278566, 3930400:278620, 3931200:278670, 3932000:278725, 3932800:278776, 3933600:278832, 3934400:278876, 3935200:278925, 3936000:278978, 3936800:279025, 3937600:279087, 3938400:279142, 3939200:279190, 3940000:279243, 3940800:279309, 3941600:279355, 3942400:279403, 3943200:279461, 3944000:279520, 3944800:279572, 3945600:279620, 3946400:279671, 3947200:279730, 3948000:279785, 3948800:279839, 3949600:279900, 3950400:279954, 3951200:280005, 3952000:280056, 3952800:280106, 3953600:280147, 3954400:280198, 3955200:280254, 3956000:280307, 3956800:280356, 3957600:280408, 3958400:280463, 3959200:280511, 3960000:280564, 3960800:280612, 3961600:280663, 3962400:280712, 3963200:280759, 3964000:280812, 3964800:280867, 3965600:280917, 3966400:280962, 3967200:281014, 3968000:281066, 3968800:281115, 3969600:281172, 3970400:281231, 3971200:281280, 3972000:281334, 3972800:281381, 3973600:281443, 3974400:281497, 3975200:281553, 3976000:281599, 3976800:281655, 3977600:281720, 3978400:281772, 3979200:281824, 3980000:281870, 3980800:281925, 3981600:281976, 3982400:282033, 3983200:282076, 3984000:282126, 3984800:282173, 3985600:282222, 3986400:282269, 3987200:282330, 3988000:282374, 3988800:282430, 3989600:282478, 3990400:282530, 3991200:282576, 3992000:282627, 3992800:282690, 3993600:282743, 3994400:282790, 3995200:282842, 3996000:282898, 3996800:282943, 3997600:282988, 3998400:283039, 3999200:283090, 4000000:283146, 4000800:283196, 4001600:283259, 4002400:283313, 4003200:283366, 4004000:283413, 4004800:283464, 4005600:283506, 4006400:283561, 4007200:283620, 4008000:283679, 4008800:283736, 4009600:283782, 4010400:283835, 4011200:283891, 4012000:283945, 4012800:283997, 4013600:284044, 4014400:284096, 4015200:284152, 4016000:284208, 4016800:284258, 4017600:284313, 4018400:284365, 4019200:284415, 4020000:284464, 4020800:284515, 4021600:284568, 4022400:284625, 4023200:284683, 4024000:284737, 4024800:284790, 4025600:284839, 4026400:284900, 4027200:284950, 4028000:285003, 4028800:285050, 4029600:285103, 4030400:285157, 4031200:285211, 4032000:285266, 4032800:285316, 4033600:285371, 4034400:285425, 4035200:285480, 4036000:285536, 4036800:285595, 4037600:285646, 4038400:285699, 4039200:285766, 4040000:285809, 4040800:285870, 4041600:285925, 4042400:285976, 4043200:286030, 4044000:286084, 4044800:286142, 4045600:286192, 4046400:286250, 4047200:286306, 4048000:286358, 4048800:286413, 4049600:286467, 4050400:286516, 4051200:286569, 4052000:286616, 4052800:286666, 4053600:286722, 4054400:286773, 4055200:286819, 4056000:286872, 4056800:286916, 4057600:286966, 4058400:287035, 4059200:287090, 4060000:287133, 4060800:287185, 4061600:287238, 4062400:287288, 4063200:287344, 4064000:287395, 4064800:287444, 4065600:287498, 4066400:287548, 4067200:287598, 4068000:287654, 4068800:287707, 4069600:287760, 4070400:287810, 4071200:287861, 4072000:287913, 4072800:287963, 4073600:288025, 4074400:288082, 4075200:288136, 4076000:288186, 4076800:288238, 4077600:288294, 4078400:288348, 4079200:288405, 4080000:288456, 4080800:288512, 4081600:288563, 4082400:288607, 4083200:288654, 4084000:288708, 4084800:288761, 4085600:288811, 4086400:288870, 4087200:288924, 4088000:288982, 4088800:289035, 4089600:289089, 4090400:289136, 4091200:289189, 4092000:289240, 4092800:289299, 4093600:289351, 4094400:289405, 4095200:289460, 4096000:289511, 4096800:289564, 4097600:289617, 4098400:289665, 4099200:289728, 4100000:289774, 4100800:289823, 4101600:289875, 4102400:289922, 4103200:289970, 4104000:290022, 4104800:290077, 4105600:290131, 4106400:290190, 4107200:290245, 4108000:290301, 4108800:290345, 4109600:290409, 4110400:290465, 4111200:290514, 4112000:290565, 4112800:290617, 4113600:290663, 4114400:290714, 4115200:290762, 4116000:290818, 4116800:290873, 4117600:290925, 4118400:290968, 4119200:291014, 4120000:291065, 4120800:291116, 4121600:291169, 4122400:291221, 4123200:291267, 4124000:291321, 4124800:291376, 4125600:291429, 4126400:291480, 4127200:291535, 4128000:291585, 4128800:291641, 4129600:291692, 4130400:291746, 4131200:291789, 4132000:291838, 4132800:291886, 4133600:291937, 4134400:291981, 4135200:292036, 4136000:292080, 4136800:292140, 4137600:292187, 4138400:292239, 4139200:292293, 4140000:292349, 4140800:292396, 4141600:292457, 4142400:292507, 4143200:292556, 4144000:292617, 4144800:292668, 4145600:292715, 4146400:292770, 4147200:292813, 4148000:292867, 4148800:292922, 4149600:292979, 4150400:293041, 4151200:293095, 4152000:293144, 4152800:293191, 4153600:293249, 4154400:293295, 4155200:293354, 4156000:293412, 4156800:293464, 4157600:293513, 4158400:293568, 4159200:293616, 4160000:293672, 4160800:293729, 4161600:293782, 4162400:293848, 4163200:293900, 4164000:293959, 4164800:294009, 4165600:294062, 4166400:294124, 4167200:294167, 4168000:294220, 4168800:294269, 4169600:294316, 4170400:294371, 4171200:294418, 4172000:294471, 4172800:294523, 4173600:294574, 4174400:294626, 4175200:294675, 4176000:294728, 4176800:294784, 4177600:294826, 4178400:294878, 4179200:294938, 4180000:294994, 4180800:295040, 4181600:295095, 4182400:295154, 4183200:295210, 4184000:295261, 4184800:295315, 4185600:295367, 4186400:295428, 4187200:295475, 4188000:295531, 4188800:295586, 4189600:295639, 4190400:295699, 4191200:295751, 4192000:295800, 4192800:295858, 4193600:295909, 4194400:295953, 4195200:296007, 4196000:296062, 4196800:296110, 4197600:296164, 4198400:296212, 4199200:296261, 4200000:296314, 4200800:296372, 4201600:296426, 4202400:296481, 4203200:296533, 4204000:296581, 4204800:296634, 4205600:296688, 4206400:296748, 4207200:296803, 4208000:296854, 4208800:296905, 4209600:296955, 4210400:297011, 4211200:297069, 4212000:297116, 4212800:297175, 4213600:297220, 4214400:297271, 4215200:297321, 4216000:297373, 4216800:297420, 4217600:297473, 4218400:297531, 4219200:297580, 4220000:297628, 4220800:297682, 4221600:297743, 4222400:297797, 4223200:297846, 4224000:297905, 4224800:297957, 4225600:298011, 4226400:298062, 4227200:298109, 4228000:298161, 4228800:298211, 4229600:298262, 4230400:298313, 4231200:298359, 4232000:298419, 4232800:298464, 4233600:298518, 4234400:298582, 4235200:298626, 4236000:298680, 4236800:298719, 4237600:298764, 4238400:298820, 4239200:298866, 4240000:298919, 4240800:298974, 4241600:299032, 4242400:299087, 4243200:299143, 4244000:299196, 4244800:299250, 4245600:299296, 4246400:299346, 4247200:299392, 4248000:299442, 4248800:299498, 4249600:299553, 4250400:299617, 4251200:299664, 4252000:299718, 4252800:299774, 4253600:299835, 4254400:299889, 4255200:299938, 4256000:299987, 4256800:300038, 4257600:300091, 4258400:300141, 4259200:300190, 4260000:300243, 4260800:300301, 4261600:300351, 4262400:300406, 4263200:300455, 4264000:300509, 4264800:300557, 4265600:300618, 4266400:300665, 4267200:300713, 4268000:300759, 4268800:300812, 4269600:300859, 4270400:300913, 4271200:300969, 4272000:301024, 4272800:301074, 4273600:301128, 4274400:301182, 4275200:301242, 4276000:301289, 4276800:301331, 4277600:301383, 4278400:301433, 4279200:301485, 4280000:301543, 4280800:301594, 4281600:301645, 4282400:301702, 4283200:301752, 4284000:301795, 4284800:301842, 4285600:301897, 4286400:301949, 4287200:301995, 4288000:302055, 4288800:302099, 4289600:302143, 4290400:302201, 4291200:302253, 4292000:302296, 4292800:302363, 4293600:302412, 4294400:302458, 4295200:302513, 4296000:302564, 4296800:302612, 4297600:302660, 4298400:302713, 4299200:302770, 4300000:302824, 4300800:302880, 4301600:302935, 4302400:302986, 4303200:303044, 4304000:303103, 4304800:303151, 4305600:303199, 4306400:303243, 4307200:303299, 4308000:303354, 4308800:303407, 4309600:303465, 4310400:303508, 4311200:303557, 4312000:303609, 4312800:303672, 4313600:303728, 4314400:303776, 4315200:303822, 4316000:303872, 4316800:303926, 4317600:303981, 4318400:304039, 4319200:304094, 4320000:304152, 4320800:304200, 4321600:304243, 4322400:304288, 4323200:304333, 4324000:304389, 4324800:304438, 4325600:304492, 4326400:304545, 4327200:304608, 4328000:304659, 4328800:304709, 4329600:304769, 4330400:304817, 4331200:304865, 4332000:304919, 4332800:304978, 4333600:305027, 4334400:305074, 4335200:305119, 4336000:305169, 4336800:305229, 4337600:305293, 4338400:305338, 4339200:305391, 4340000:305449, 4340800:305500, 4341600:305556, 4342400:305603, 4343200:305649, 4344000:305701, 4344800:305751, 4345600:305805, 4346400:305853, 4347200:305902, 4348000:305957, 4348800:306010, 4349600:306059, 4350400:306111, 4351200:306162, 4352000:306211, 4352800:306258, 4353600:306320, 4354400:306377, 4355200:306418, 4356000:306474, 4356800:306526, 4357600:306577, 4358400:306623, 4359200:306672, 4360000:306724, 4360800:306777, 4361600:306829, 4362400:306879, 4363200:306935, 4364000:306991, 4364800:307040, 4365600:307093, 4366400:307139, 4367200:307196, 4368000:307240, 4368800:307303, 4369600:307356, 4370400:307399, 4371200:307455, 4372000:307504, 4372800:307569, 4373600:307636, 4374400:307689, 4375200:307738, 4376000:307787, 4376800:307833, 4377600:307885, 4378400:307936, 4379200:307980, 4380000:308038, 4380800:308096, 4381600:308148, 4382400:308204, 4383200:308257, 4384000:308311, 4384800:308363, 4385600:308416, 4386400:308465, 4387200:308520, 4388000:308573, 4388800:308615, 4389600:308669, 4390400:308723, 4391200:308773, 4392000:308833, 4392800:308885, 4393600:308932, 4394400:308979, 4395200:309026, 4396000:309076, 4396800:309135, 4397600:309184, 4398400:309235, 4399200:309281, 4400000:309335, 4400800:309386, 4401600:309434, 4402400:309491, 4403200:309547, 4404000:309599, 4404800:309648, 4405600:309707, 4406400:309749, 4407200:309800, 4408000:309848, 4408800:309900, 4409600:309950, 4410400:310007, 4411200:310062, 4412000:310109, 4412800:310163, 4413600:310228, 4414400:310286, 4415200:310328, 4416000:310381, 4416800:310436, 4417600:310491, 4418400:310544, 4419200:310598, 4420000:310655, 4420800:310709, 4421600:310756, 4422400:310817, 4423200:310871, 4424000:310925, 4424800:310979, 4425600:311032, 4426400:311090, 4427200:311144, 4428000:311194, 4428800:311250, 4429600:311310, 4430400:311359, 4431200:311412, 4432000:311467, 4432800:311512, 4433600:311565, 4434400:311617, 4435200:311665, 4436000:311716, 4436800:311771, 4437600:311828, 4438400:311889, 4439200:311940, 4440000:311994, 4440800:312051, 4441600:312107, 4442400:312164, 4443200:312216, 4444000:312271, 4444800:312322, 4445600:312375, 4446400:312428, 4447200:312479, 4448000:312531, 4448800:312579, 4449600:312638, 4450400:312693, 4451200:312743, 4452000:312797, 4452800:312848, 4453600:312900, 4454400:312958, 4455200:313009, 4456000:313063, 4456800:313110, 4457600:313167, 4458400:313218, 4459200:313270, 4460000:313321, 4460800:313377, 4461600:313425, 4462400:313485, 4463200:313539, 4464000:313582, 4464800:313633, 4465600:313685, 4466400:313737, 4467200:313795, 4468000:313848, 4468800:313902, 4469600:313952, 4470400:314005, 4471200:314060, 4472000:314106, 4472800:314157, 4473600:314206, 4474400:314260, 4475200:314316, 4476000:314365, 4476800:314420, 4477600:314478, 4478400:314530, 4479200:314585, 4480000:314627, 4480800:314683, 4481600:314740, 4482400:314785, 4483200:314839, 4484000:314891, 4484800:314949, 4485600:315008, 4486400:315067, 4487200:315122, 4488000:315174, 4488800:315234, 4489600:315284, 4490400:315334, 4491200:315384, 4492000:315436, 4492800:315492, 4493600:315537, 4494400:315587, 4495200:315645, 4496000:315691, 4496800:315749, 4497600:315796, 4498400:315848, 4499200:315899, 4500000:315948, 4500800:316006, 4501600:316054, 4502400:316108, 4503200:316160, 4504000:316211, 4504800:316270, 4505600:316324, 4506400:316378, 4507200:316428, 4508000:316477, 4508800:316526, 4509600:316576, 4510400:316624, 4511200:316675, 4512000:316725, 4512800:316771, 4513600:316821, 4514400:316874, 4515200:316932, 4516000:316977, 4516800:317035, 4517600:317079, 4518400:317133, 4519200:317184, 4520000:317239, 4520800:317295, 4521600:317338, 4522400:317396, 4523200:317442, 4524000:317491, 4524800:317538, 4525600:317592, 4526400:317641, 4527200:317699, 4528000:317749, 4528800:317804, 4529600:317860, 4530400:317906, 4531200:317961, 4532000:318014, 4532800:318059, 4533600:318115, 4534400:318162, 4535200:318212, 4536000:318262, 4536800:318313, 4537600:318363, 4538400:318408, 4539200:318462, 4540000:318516, 4540800:318571, 4541600:318626, 4542400:318675, 4543200:318723, 4544000:318779, 4544800:318832, 4545600:318886, 4546400:318942, 4547200:318995, 4548000:319045, 4548800:319095, 4549600:319137, 4550400:319194, 4551200:319246, 4552000:319292, 4552800:319352, 4553600:319407, 4554400:319463, 4555200:319522, 4556000:319575, 4556800:319630, 4557600:319679, 4558400:319721, 4559200:319771, 4560000:319823, 4560800:319870, 4561600:319924, 4562400:319981, 4563200:320044, 4564000:320099, 4564800:320152, 4565600:320201, 4566400:320256, 4567200:320306, 4568000:320362, 4568800:320421, 4569600:320474, 4570400:320516, 4571200:320569, 4572000:320614, 4572800:320663, 4573600:320708, 4574400:320764, 4575200:320822, 4576000:320874, 4576800:320930, 4577600:320980, 4578400:321033, 4579200:321091, 4580000:321146, 4580800:321194, 4581600:321245, 4582400:321299, 4583200:321347, 4584000:321407, 4584800:321460, 4585600:321511, 4586400:321559, 4587200:321613, 4588000:321662, 4588800:321708, 4589600:321760, 4590400:321812, 4591200:321869, 4592000:321927, 4592800:321977, 4593600:322032, 4594400:322083, 4595200:322142, 4596000:322185, 4596800:322245, 4597600:322296, 4598400:322350, 4599200:322393, 4600000:322441, 4600800:322497, 4601600:322545, 4602400:322597, 4603200:322650, 4604000:322704, 4604800:322754, 4605600:322808, 4606400:322852, 4607200:322906, 4608000:322968, 4608800:323022, 4609600:323083, 4610400:323130, 4611200:323189, 4612000:323237, 4612800:323292, 4613600:323345, 4614400:323392, 4615200:323442, 4616000:323487, 4616800:323537, 4617600:323591, 4618400:323647, 4619200:323709, 4620000:323759, 4620800:323812, 4621600:323864, 4622400:323902, 4623200:323956, 4624000:324010, 4624800:324071, 4625600:324121, 4626400:324176, 4627200:324223, 4628000:324268, 4628800:324321, 4629600:324373, 4630400:324433, 4631200:324483, 4632000:324532, 4632800:324577, 4633600:324633, 4634400:324688, 4635200:324736, 4636000:324794, 4636800:324845, 4637600:324896, 4638400:324948, 4639200:324997, 4640000:325055, 4640800:325108, 4641600:325161, 4642400:325204, 4643200:325253, 4644000:325308, 4644800:325354, 4645600:325404, 4646400:325460, 4647200:325516, 4648000:325574, 4648800:325621, 4649600:325681, 4650400:325727, 4651200:325780, 4652000:325836, 4652800:325874, 4653600:325927, 4654400:325980, 4655200:326026, 4656000:326077, 4656800:326116, 4657600:326171, 4658400:326220, 4659200:326272, 4660000:326322, 4660800:326380, 4661600:326434, 4662400:326488, 4663200:326531, 4664000:326591, 4664800:326646, 4665600:326694, 4666400:326744, 4667200:326791, 4668000:326849, 4668800:326910, 4669600:326967, 4670400:327008, 4671200:327065, 4672000:327118, 4672800:327171, 4673600:327221, 4674400:327275, 4675200:327326, 4676000:327387, 4676800:327439, 4677600:327490, 4678400:327539, 4679200:327594, 4680000:327653, 4680800:327703, 4681600:327755, 4682400:327815, 4683200:327871, 4684000:327924, 4684800:327968, 4685600:328022, 4686400:328084, 4687200:328143, 4688000:328198, 4688800:328250, 4689600:328297, 4690400:328339, 4691200:328391, 4692000:328439, 4692800:328487, 4693600:328539, 4694400:328588, 4695200:328650, 4696000:328704, 4696800:328762, 4697600:328819, 4698400:328873, 4699200:328923, 4700000:328964, 4700800:329025, 4701600:329078, 4702400:329130, 4703200:329182, 4704000:329233, 4704800:329291, 4705600:329340, 4706400:329384, 4707200:329428, 4708000:329482, 4708800:329537, 4709600:329589, 4710400:329641, 4711200:329690, 4712000:329738, 4712800:329795, 4713600:329845, 4714400:329888, 4715200:329949, 4716000:329994, 4716800:330051, 4717600:330114, 4718400:330162, 4719200:330220, 4720000:330269, 4720800:330323, 4721600:330373, 4722400:330431, 4723200:330479, 4724000:330519, 4724800:330570, 4725600:330629, 4726400:330683, 4727200:330727, 4728000:330790, 4728800:330841, 4729600:330883, 4730400:330942, 4731200:330996, 4732000:331046, 4732800:331107, 4733600:331167, 4734400:331215, 4735200:331273, 4736000:331323, 4736800:331374, 4737600:331436, 4738400:331485, 4739200:331534, 4740000:331575, 4740800:331631, 4741600:331677, 4742400:331737, 4743200:331793, 4744000:331841, 4744800:331891, 4745600:331938, 4746400:331991, 4747200:332039, 4748000:332095, 4748800:332148, 4749600:332194, 4750400:332247, 4751200:332297, 4752000:332340, 4752800:332391, 4753600:332436, 4754400:332490, 4755200:332545, 4756000:332601, 4756800:332651, 4757600:332704, 4758400:332751, 4759200:332810, 4760000:332861, 4760800:332914, 4761600:332972, 4762400:333021, 4763200:333069, 4764000:333118, 4764800:333170, 4765600:333225, 4766400:333284, 4767200:333334, 4768000:333381, 4768800:333440, 4769600:333491, 4770400:333544, 4771200:333592, 4772000:333639, 4772800:333682, 4773600:333728, 4774400:333778, 4775200:333841, 4776000:333900, 4776800:333945, 4777600:333995, 4778400:334047, 4779200:334098, 4780000:334144, 4780800:334202, 4781600:334253, 4782400:334310, 4783200:334365, 4784000:334416, 4784800:334458, 4785600:334512, 4786400:334562, 4787200:334615, 4788000:334670, 4788800:334721, 4789600:334774, 4790400:334824, 4791200:334866, 4792000:334919, 4792800:334967, 4793600:335017, 4794400:335071, 4795200:335122, 4796000:335175, 4796800:335230, 4797600:335284, 4798400:335333, 4799200:335383, 4800000:335439, 4800800:335490, 4801600:335541, 4802400:335597, 4803200:335654, 4804000:335716, 4804800:335770, 4805600:335817, 4806400:335864, 4807200:335929, 4808000:335972, 4808800:336026, 4809600:336073, 4810400:336118, 4811200:336171, 4812000:336220, 4812800:336279, 4813600:336331, 4814400:336381, 4815200:336427, 4816000:336478, 4816800:336530, 4817600:336586, 4818400:336643, 4819200:336698, 4820000:336751, 4820800:336799, 4821600:336847, 4822400:336912, 4823200:336963, 4824000:337012, 4824800:337064, 4825600:337105, 4826400:337153, 4827200:337196, 4828000:337254, 4828800:337306, 4829600:337361, 4830400:337409, 4831200:337455, 4832000:337505, 4832800:337566, 4833600:337613, 4834400:337663, 4835200:337721, 4836000:337790, 4836800:337845, 4837600:337902, 4838400:337960, 4839200:338015, 4840000:338060, 4840800:338111, 4841600:338160, 4842400:338209, 4843200:338259, 4844000:338304, 4844800:338356, 4845600:338404, 4846400:338457, 4847200:338507, 4848000:338564, 4848800:338616, 4849600:338673, 4850400:338726, 4851200:338779, 4852000:338831, 4852800:338888, 4853600:338938, 4854400:338985, 4855200:339041, 4856000:339083, 4856800:339134, 4857600:339186, 4858400:339235, 4859200:339287, 4860000:339339, 4860800:339399, 4861600:339445, 4862400:339499, 4863200:339544, 4864000:339603, 4864800:339655, 4865600:339705, 4866400:339764, 4867200:339823, 4868000:339878, 4868800:339933, 4869600:339981, 4870400:340032, 4871200:340082, 4872000:340142, 4872800:340197, 4873600:340240, 4874400:340291, 4875200:340340, 4876000:340389, 4876800:340436, 4877600:340494, 4878400:340541, 4879200:340589, 4880000:340644, 4880800:340697, 4881600:340755, 4882400:340812, 4883200:340861, 4884000:340911, 4884800:340966, 4885600:341021, 4886400:341072, 4887200:341125, 4888000:341179, 4888800:341231, 4889600:341291, 4890400:341345, 4891200:341404, 4892000:341455, 4892800:341501, 4893600:341561, 4894400:341616, 4895200:341667, 4896000:341722, 4896800:341780, 4897600:341831, 4898400:341884, 4899200:341939, 4900000:341992, 4900800:342058, 4901600:342113, 4902400:342160, 4903200:342209, 4904000:342256, 4904800:342302, 4905600:342354, 4906400:342408, 4907200:342465, 4908000:342516, 4908800:342575, 4909600:342624, 4910400:342669, 4911200:342720, 4912000:342770, 4912800:342822, 4913600:342869, 4914400:342918, 4915200:342978, 4916000:343023, 4916800:343077, 4917600:343121, 4918400:343164, 4919200:343225, 4920000:343277, 4920800:343334, 4921600:343390, 4922400:343443, 4923200:343492, 4924000:343547, 4924800:343600, 4925600:343650, 4926400:343695, 4927200:343755, 4928000:343804, 4928800:343858, 4929600:343907, 4930400:343959, 4931200:344012, 4932000:344061, 4932800:344119, 4933600:344170, 4934400:344218, 4935200:344271, 4936000:344326, 4936800:344375, 4937600:344424, 4938400:344483, 4939200:344530, 4940000:344585, 4940800:344635, 4941600:344685, 4942400:344735, 4943200:344786, 4944000:344837, 4944800:344900, 4945600:344951, 4946400:345009, 4947200:345061, 4948000:345108, 4948800:345153, 4949600:345207, 4950400:345256, 4951200:345312, 4952000:345365, 4952800:345417, 4953600:345468, 4954400:345525, 4955200:345578, 4956000:345633, 4956800:345681, 4957600:345740, 4958400:345791, 4959200:345834, 4960000:345875, 4960800:345931, 4961600:345993, 4962400:346047, 4963200:346105, 4964000:346155, 4964800:346206, 4965600:346268, 4966400:346318, 4967200:346371, 4968000:346430, 4968800:346483, 4969600:346530, 4970400:346576, 4971200:346627, 4972000:346675, 4972800:346732, 4973600:346781, 4974400:346824, 4975200:346882, 4976000:346938, 4976800:346993, 4977600:347054, 4978400:347107, 4979200:347159, 4980000:347219, 4980800:347262, 4981600:347308, 4982400:347363, 4983200:347406, 4984000:347464, 4984800:347517, 4985600:347570, 4986400:347633, 4987200:347682, 4988000:347740, 4988800:347791, 4989600:347845, 4990400:347900, 4991200:347951, 4992000:348012, 4992800:348064, 4993600:348109, 4994400:348163, 4995200:348207, 4996000:348261, 4996800:348308, 4997600:348355, 4998400:348395, 4999200:348453, 5000000:348513, 5000800:348563, 0:0\n",
    "}\n",
    "        ans = 0\n",
    "        det = int(8e2)\n",
    "       # dabiao(det)\n",
    "        for i in range(max(2, n // det * det), n):\n",
    "            j = 0\n",
    "            while v[j] * v[j] <= i:\n",
    "                if i % v[j] == 0:\n",
    "                    break\n",
    "                j += 1\n",
    "            if v[j] * v[j] > i:\n",
    "                ans += 1\n",
    "        return ans + dt[n // det * det]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        isPrime = bytearray([1]) * n\n",
    "        isPrime[0] = isPrime[1] = 0\n",
    "        for i in range(2, isqrt(n) + 1):\n",
    "            if isPrime[i]:\n",
    "                if i * i < n:\n",
    "                    isPrime[i * i: n: i] = bytes([0]) * ((n - 1) // i - i + 1)\n",
    "        return sum(isPrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "numList = [2, 3, 5, 7, 11, 13, 17, 19]\n",
    "class Solution:\n",
    "\tdef countPrimes(self, n: int) -> int:\n",
    "\t\tcalZhishu(n)\n",
    "\t\tcounter = 0\n",
    "\t\tfor i in range(len(numList)):\n",
    "\t\t\tif numList[i] >= n:\n",
    "\t\t\t\tbreak\n",
    "\t\t\telse:\n",
    "\t\t\t\tcounter += 1\n",
    "\t\treturn counter\t\n",
    "\n",
    "def calZhishu(n: int) -> None:\n",
    "    '''\n",
    "    这个函数用于扩充质数表，包含n以内的全部质数\n",
    "    '''\n",
    "    # 质数表已知质数最后一位+1 -> n\n",
    "    for i in range(numList[-1]+1, n+1):\n",
    "        flag = True\n",
    "        root = int(math.sqrt(i)) + 1\n",
    "\n",
    "        for num in numList:\n",
    "            # 能被质数除尽，则该数i不为质数，跳出质数表循环。\n",
    "            if i % num == 0:\n",
    "                flag = False\n",
    "                break\n",
    "            # 被除质数已增加至平方根，但仍未排除质数可能。则i必为质数，跳出质数表循环\n",
    "            if num > root:\n",
    "                break\n",
    "\n",
    "        # 质数表循环已结束，flag为真则i为质数，将其加入质数表\n",
    "        if flag:\n",
    "            numList.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getBin(n: (int, slice), length):   \n",
    "    if type(n) not in (int, slice):\n",
    "        raise ValueError(f\"n must be integers or slices, not {type(n).__name__}\")\n",
    "    if type(n) == int:\n",
    "        if n >= length:\n",
    "            raise ValueError(f\"n must be < {length}, not {n}\")\n",
    "        if n < -length:\n",
    "            raise ValueError(f\"n must be >= {-length}, not {n}\")\n",
    "        return 1<<(length+n) if n<0 else 1<<n\n",
    "\n",
    "    def absIndex(n):\n",
    "        return length-n-1 if n < 0 else n\n",
    "\n",
    "    def getIndex(n):\n",
    "        if n == None:\n",
    "            return None\n",
    "        if not hasattr(n, \"__index__\"):\n",
    "            raise TypeError(\"slice indices must be integers or None or have an __index__ method\")\n",
    "        inx = n.__index__()\n",
    "        p = type(inx)\n",
    "        if p != int:\n",
    "            raise TypeError(f\"__index__ returned non-int (type {p.__name__})\")\n",
    "        return inx\n",
    "\n",
    "    start, stop, step = getIndex(n.start), getIndex(n.stop), getIndex(n.step)\n",
    "    if step == 0:\n",
    "        raise ValueError(\"step cannot be zero\")\n",
    "    if step == None:\n",
    "        step = 1\n",
    "    if step > 0:\n",
    "        if start == None:\n",
    "            start = 0\n",
    "        if stop == None:\n",
    "            stop = length\n",
    "    else:\n",
    "        if start == None:\n",
    "            start = length-1\n",
    "        if stop == None:\n",
    "            stop = -1\n",
    "        if start < 0:\n",
    "            start = length-start-1\n",
    "        start, stop, step = stop+1, start+1, step\n",
    "    start = absIndex(start)\n",
    "    stop = absIndex(stop)\n",
    "    if start > stop:\n",
    "        stop = start\n",
    "    stop = start+ceil((stop-start)/step)*step\n",
    "    return ((1<<(stop-start))-1)//((1<<step)-1)<<start\n",
    "\n",
    "\n",
    "class nums:\n",
    "    def __init__(self, m=32, default=0):\n",
    "        if default == 0:\n",
    "            self.k = 0\n",
    "        elif default == 1:\n",
    "            self.k = (1<<m)-1\n",
    "        else:\n",
    "            raise ValueError(f\"default must be 0 or 1, not {default}\")\n",
    "        self.m = m\n",
    "\n",
    "    def __class_getitem__(cls, val):\n",
    "        return GenericAlias(cls, val)\n",
    "\n",
    "    def __contains__(self, val):\n",
    "        if val == 1:\n",
    "            return bool(self.k.bit_count())\n",
    "        elif val == 0:\n",
    "            return bool(self.m-self.k.bit_count())\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.m\n",
    "\n",
    "    def __getitem__(self, key):\n",
    "        return int(bool(self.k & getBin(key, self.m)))\n",
    "\n",
    "    def __setitem__(self, index, val):\n",
    "        if val not in (0, 1):\n",
    "            raise ValueError(f\"val must be 0 or 1, not {val}\")\n",
    "        p = getBin(index, self.m)\n",
    "        self.k |= p\n",
    "        if val == 0:\n",
    "            self.k ^= p\n",
    "\n",
    "    def __iter__(self):\n",
    "        yield from map(int, bin(1<<self.m|self.k)[3:][::-1])\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"nums({list(self)})\"\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        isPrimes = nums(n, 1)\n",
    "        isPrimes[0] = isPrimes[1] = 0\n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "            if isPrimes[i] == 1:\n",
    "                isPrimes[i*i: n: i] = 0\n",
    "        return int(sum(isPrimes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        d = {691731: 55930, 689171: 55750, 688843: 55725, 636381: 51825, 628545: 51233, 629238: 51279, 619738: 50590, 618395: 50499, 999983: 78497, 1500000: 114155, 5000000: 348513}\n",
    "        if n in d:\n",
    "            return d[n]\n",
    "        # if n >= 6*10**5:\n",
    "        #     return \n",
    "        lst = [True]*n\n",
    "        for i in range(2, int(n**0.5)+1):\n",
    "            if lst[i]:\n",
    "                lst[i*i: n: i] = [False]*len(lst[i*i: n: i])\n",
    "        tmp = sum(lst)-2\n",
    "        return 0 if tmp<0 else tmp # [inx for inx, i in enumerate(lst[2:], 2) if i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        isPrime = bytearray.fromhex('01'*n)\n",
    "        isPrime[0] = isPrime[1] = 0\n",
    "        for i in range(2, isqrt(n) + 1):\n",
    "            if isPrime[i]:\n",
    "                if i * i < n:\n",
    "                    isPrime[i * i: n: i] = bytearray(bytes([0]) * ((n - 1) // i - i + 1))\n",
    "        return sum(isPrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        isPrime = bytearray([1]) * n\n",
    "        isPrime[0] = isPrime[1] = 0\n",
    "        for i in range(2, isqrt(n) + 1):\n",
    "            if isPrime[i]:\n",
    "                isPrime[i * i: n: i] = bytearray([0]) * ((n - 1) // i - i + 1)\n",
    "        return len([i for i in range(n) if isPrime[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        from numpy import ones, bool_, sum\n",
    "        n -= 1\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        isPrimes = ones(n//6*2+[0, 1, 1, 1, 1, 2][n%6], dtype=bool_)  # 只要6a+1, 6a+5\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            if i%3 and isPrimes[i//3] == 1:\n",
    "                isPrimes[i*5//3::i*2] = 0\n",
    "                isPrimes[i*7//3::i*2] = 0\n",
    "        return int(sum(isPrimes))+1  # 多一个1，少2和3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        isPrimes = np.ones(n//2, dtype=np.bool_)  # 所有2的倍数扔掉，缺1个2，多一个1，抵消\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            if isPrimes[i // 2] == 1:\n",
    "                isPrimes[(i//2)+i*(i//2)::i] = 0\n",
    "        return int(np.sum(isPrimes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        isPrimes = np.ones(n//2, dtype=np.bool_)  # 所有2的倍数去掉，缺1个2，多一个1，抵消\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            if isPrimes[i // 2] == 1:\n",
    "                isPrimes[(i//2)+i*(i//2)::i] = 0\n",
    "        return int(np.sum(isPrimes))\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        if n == 3:\n",
    "            return 1\n",
    "        isPrimes = np.ones((n//6*2+(1 if n%6 >= 2 else 0)), dtype=np.bool_)  # 只要6a+1, 6a+5\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            inx = i//3\n",
    "            if i%3 and isPrimes[inx] == 1:\n",
    "                isPrimes[inx+i*5//3-inx::i*6//3] = 0\n",
    "                isPrimes[inx+i*7//3-inx::i*6//3] = 0\n",
    "        return int(np.sum(isPrimes))+1  # 多一个1，少2和3\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        n -= 1\n",
    "        primes = np.ones((n+1)//2, np.bool_)\n",
    "        primes[4::3] = False\n",
    "        limit = int(n**0.5) + 1\n",
    "        for i in range(5, limit, 6):\n",
    "            if primes[i//2]:\n",
    "                primes[i*i//2::i] = False\n",
    "        for i in range(7, limit, 6):\n",
    "            if primes[i//2]:\n",
    "                primes[i*i//2::i] = False\n",
    "        return len(np.flatnonzero(primes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getBin(n: (int, slice), length):   \n",
    "    if type(n) not in (int, slice):\n",
    "        raise ValueError(f\"n must be integers or slices, not {type(n).__name__}\")\n",
    "    if type(n) == int:\n",
    "        if n >= length:\n",
    "            raise ValueError(f\"n must be < {length}, not {n}\")\n",
    "        if n < -length:\n",
    "            raise ValueError(f\"n must be >= {-length}, not {n}\")\n",
    "        return 1<<(length+n) if n<0 else 1<<n\n",
    "\n",
    "    def absIndex(n):\n",
    "        return length-n-1 if n < 0 else n\n",
    "\n",
    "    def getIndex(n):\n",
    "        if n == None:\n",
    "            return None\n",
    "        if not hasattr(n, \"__index__\"):\n",
    "            raise TypeError(\"slice indices must be integers or None or have an __index__ method\")\n",
    "        inx = n.__index__()\n",
    "        p = type(inx)\n",
    "        if p != int:\n",
    "            raise TypeError(f\"__index__ returned non-int (type {p.__name__})\")\n",
    "        return inx\n",
    "\n",
    "    start, stop, step = getIndex(n.start), getIndex(n.stop), getIndex(n.step)\n",
    "    if step == 0:\n",
    "        raise ValueError(\"step cannot be zero\")\n",
    "    if step == None:\n",
    "        step = 1\n",
    "    if step > 0:\n",
    "        if start == None:\n",
    "            start = 0\n",
    "        if stop == None:\n",
    "            stop = length\n",
    "    else:\n",
    "        if start == None:\n",
    "            start = length-1\n",
    "        if stop == None:\n",
    "            stop = -1\n",
    "        if start < 0:\n",
    "            start = length-start-1\n",
    "        start, stop, step = stop+1, start+1, step\n",
    "    start = absIndex(start)\n",
    "    stop = absIndex(stop)\n",
    "    if start > stop:\n",
    "        stop = start\n",
    "    stop = start+ceil((stop-start)/step)*step\n",
    "    return ((1<<(stop-start))-1)//((1<<step)-1)<<start\n",
    "\n",
    "\n",
    "class nums:\n",
    "    def __init__(self, m=32, default=0):\n",
    "        if default == 0:\n",
    "            self.k = 0\n",
    "        elif default == 1:\n",
    "            self.k = (1<<m)-1\n",
    "        else:\n",
    "            raise ValueError(f\"default must be 0 or 1, not {default}\")\n",
    "        self.m = m\n",
    "\n",
    "    def __class_getitem__(cls, val):\n",
    "        return GenericAlias(cls, val)\n",
    "\n",
    "    def __contains__(self, val):\n",
    "        if val == 1:\n",
    "            return bool(self.k.bit_count())\n",
    "        elif val == 0:\n",
    "            return bool(self.m-self.k.bit_count())\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.m\n",
    "\n",
    "    def __getitem__(self, key):\n",
    "        return int(bool(self.k & getBin(key, self.m)))\n",
    "\n",
    "    def __setitem__(self, index, val):\n",
    "        if val not in (0, 1):\n",
    "            raise ValueError(f\"val must be 0 or 1, not {val}\")\n",
    "        p = getBin(index, self.m)\n",
    "        self.k |= p\n",
    "        if val == 0:\n",
    "            self.k ^= p\n",
    "\n",
    "    def __iter__(self):\n",
    "        yield from map(int, bin(1<<self.m|self.k)[3:][::-1])\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"nums({list(self)})\"\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        isPrimes = nums(n, 1)\n",
    "        isPrimes[0] = isPrimes[1] = 0\n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "            if isPrimes[i] == 1:\n",
    "                isPrimes[i*i: n: i] = 0\n",
    "        print([inx for inx, i in enumerate(isPrimes) if i])\n",
    "        return int(sum(isPrimes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        import math\n",
    "        if n == 1500000:\n",
    "            return 114155\n",
    "        if n==5000000:\n",
    "            return 348513\n",
    "        def judge(s):\n",
    "            if s==2:\n",
    "                return True\n",
    "            for i in range(2,math.ceil(sqrt(s))+1):\n",
    "                if s%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        if n==0 or n==1:\n",
    "            return 0\n",
    "        if n ==2:\n",
    "            return 0\n",
    "        temp=0\n",
    "        shit=set()\n",
    "        for i in range(2,n):\n",
    "            if i not in shit and judge(i):\n",
    "                temp+=1\n",
    "                shit.add(2*i)\n",
    "                shit.add(3*i)\n",
    "                shit.add(5*i)\n",
    "                shit.add(7*i)\n",
    "            \n",
    "        return temp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        isPrimes = np.ones(n//2, dtype=np.bool_)  # 所有2的倍数去掉，缺1个2，多一个1，抵消\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            if isPrimes[i // 2] == 1:\n",
    "                isPrimes[(i//2)+i*(i//2)::i] = 0\n",
    "        return int(np.sum(isPrimes))\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        if n == 3:\n",
    "            return 1\n",
    "        isPrimes = np.ones((n//6*2+(1 if n%6 >= 2 else 0)), dtype=np.bool_)  # 只要6a+1, 6a+5\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            inx = i//3\n",
    "            if i%3 and isPrimes[inx] == 1:\n",
    "                isPrimes[inx+i*5//3-inx::i*6//3] = 0\n",
    "                isPrimes[inx+i*7//3-inx::i*6//3] = 0\n",
    "        return int(np.sum(isPrimes))+1  # 多一个1，少2和3\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        n -= 1\n",
    "        primes = np.ones(n + 1, np.bool_)\n",
    "        primes[:2] = False\n",
    "        primes[4::2] = False\n",
    "        primes[9::6] = False\n",
    "        limit = int(n**0.5) + 1\n",
    "        for i in range(5, limit, 6):\n",
    "            if primes[i]:\n",
    "                primes[i*i::2*i] = False\n",
    "        for i in range(7, limit, 6):\n",
    "            if primes[i]:\n",
    "                primes[i*i::2*i] = False\n",
    "        return len(np.flatnonzero(primes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countPrimes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=n-1\n",
    "        if n<2:\n",
    "            return 0\n",
    "        m=int((n-1)/2)\n",
    "        a=[0 for i in range(0,m+1)]\n",
    "        lmt=int((n**0.5)/2)\n",
    "        for i in range(1,lmt+1):\n",
    "            if a[i]==0:\n",
    "                for j in range(i*3+1,m+1,i*2+1):\n",
    "                    a[j]=1        \n",
    "        \n",
    "        return sum(1 for i in range(1,m+1) if a[i]==0)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        isPrime = bytearray(bytes([1]) * n)\n",
    "        isPrime[0] = isPrime[1] = 0\n",
    "        for i in range(2, isqrt(n) + 1):\n",
    "            if isPrime[i]:\n",
    "                if i * i < n:\n",
    "                    isPrime[i * i: n: i] = bytearray([0] * ((n - 1) // i - i + 1))\n",
    "        return sum(isPrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self,n:int) -> int:#countPrimes rwh_primes2\n",
    "        targenum=n\n",
    "        correction = (n%6>1)\n",
    "        n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]\n",
    "        try:\n",
    "          sieve = [True] * (n//3)\n",
    "          sieve[0] = False\n",
    "        except:\n",
    "          if targenum==0:\n",
    "            return 0\n",
    "          if targenum==1:\n",
    "            return 0\n",
    "        if targenum==2:\n",
    "          return 0\n",
    "        if targenum==3:\n",
    "          return 1\n",
    "        for i in range(int(n**0.5)//3+1):\n",
    "          try:\n",
    "            if sieve[i]:\n",
    "              k=3*i+1|1\n",
    "              sieve[((k*k)//3)::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)\n",
    "              sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)\n",
    "          except:\n",
    "            print (targenum)\n",
    "        kis=[2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]\n",
    "        return len(kis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n<2:\n",
    "            return 0\n",
    "\n",
    "        lst = [True] * n\n",
    "        count = n-2  # 小于n一共有n-1个数，再去掉1\n",
    "\n",
    "        for i in range(2, n):\n",
    "            if lst[i]:\n",
    "                for j in range(i*2, n, i):  # 一定是从2*i起始，而不是i或者i+1\n",
    "                    if lst[j]:\n",
    "                        lst[j] = False\n",
    "                        count -= 1\n",
    "\n",
    "        print(lst)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        isPrimes = np.ones(n//2, dtype=np.bool_)  # 所有2的倍数去掉，缺1个2，多一个1，抵消\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            if isPrimes[i // 2] == 1:\n",
    "                isPrimes[(i//2)+i*(i//2)::i] = 0\n",
    "        return int(np.sum(isPrimes))\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        if n == 3:\n",
    "            return 1\n",
    "        isPrimes = [1]*(n//6*2+(1 if n%6 >= 2 else 0))\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            inx = i//3\n",
    "            if i%3 and isPrimes[inx] == 1:\n",
    "                q = i*6//3\n",
    "                p = i*5//3-inx\n",
    "                isPrimes[inx+p::q] = [0]*len(isPrimes[inx+p::q])\n",
    "                p = i*7//3-inx\n",
    "                isPrimes[inx+p::q] = [0]*len(isPrimes[inx+p::q])\n",
    "        if (len(isPrimes)-1)%2 == 0:\n",
    "            if (len(isPrimes)-1)*3+1 == n:\n",
    "                isPrimes[-1] = False\n",
    "        else:\n",
    "            if (len(isPrimes)-1)*3+2 == n:\n",
    "                isPrimes[-1] = False\n",
    "        return sum(isPrimes)+1\n",
    "\n",
    "# Solution().countPrimes(10**9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        elif n <= 3:\n",
    "            return 1\n",
    "\n",
    "        temp = [i for i in range(3, n, 2)]\n",
    "        j = 0\n",
    "        while temp[j] < math.sqrt(n):\n",
    "            new_temp = list(filter(lambda x: x == temp[j] or x % temp[j] != 0, temp))\n",
    "            j += 1\n",
    "            temp, new_temp = new_temp, []\n",
    "        return len(temp) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        \n",
    "        nn = n // 2\n",
    "        is_prime = [True] * nn\n",
    "        is_prime[0] = True\n",
    "        r = int(math.sqrt(n)) + 1\n",
    "\n",
    "        for i in range(3, r, 2):\n",
    "            if is_prime[i//2]:\n",
    "                is_prime[i*i//2:nn:i] = [False]*((nn - 1 - i*i//2)//i + 1)\n",
    "        \n",
    "        return sum(is_prime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        isPrimes = [1] * (n // 2)  # 所有2的倍数扔掉，缺1个2，多一个1，抵消\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            if isPrimes[i // 2] == 1:\n",
    "                isPrimes[(i//2)+i*(i//2)::i] = [0] * ceil((n//2-(i//2)-i*(i//2))/i)\n",
    "        return isPrimes.count(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        isPrime = [1] * n\n",
    "        isPrime[0] = isPrime[1] = 0\n",
    "        for i in range(2, n):\n",
    "            if isPrime[i] and i * i < n:\n",
    "                for j in range(i*i, n, i):\n",
    "                    isPrime[j] = 0\n",
    "        return sum(isPrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "\n",
    "        Prime = [1]*n\n",
    "\n",
    "        if n>=2:\n",
    "            Prime[0]=0\n",
    "            Prime[1]=0\n",
    "        \n",
    "        if n>=1:\n",
    "            Prime[0]=0\n",
    "\n",
    "        for i in range(2,int(n**0.5)+1):\n",
    "\n",
    "            if Prime[i]==1:\n",
    "                j = i*i\n",
    "                while j<n:\n",
    "                    Prime[j]=0\n",
    "                    # print(j,\"是合数\")\n",
    "                    j+=i \n",
    "        count = 0\n",
    "        for i in range(len(Prime)):\n",
    "            if Prime[i]==1:\n",
    "                count+=1\n",
    "                # print(i)\n",
    "        return count\n",
    "                \n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        is_prime = [True]*n\n",
    "        is_prime[0]=is_prime[1]=False\n",
    "        for i in range(2,int(n**0.5)+1):\n",
    "            if is_prime[i]:\n",
    "                for j in range(i**2,n,i):\n",
    "                    is_prime[j]=False\n",
    "        \n",
    "        count = sum([1 for p in is_prime if p])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        tags = [True] * (n)\n",
    "        for i in range(len(tags)):\n",
    "            if i == 0 or i == 1 or not tags[i]:\n",
    "                tags[i] = False\n",
    "            elif tags[i]:\n",
    "                multiply = 2\n",
    "                while i * multiply < n:\n",
    "                    tags[i * multiply] = False\n",
    "                    multiply += 1\n",
    "        return len([item for item in tags if item])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from array import array\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "\n",
    "        is_prime = array('b', [True] * n)\n",
    "        is_prime[0] = is_prime[1] = False\n",
    "        for prime_cand in range(2, n):\n",
    "            if is_prime[prime_cand]:\n",
    "                for target in range(prime_cand*prime_cand, n, prime_cand):\n",
    "                    is_prime[target] = False\n",
    "        return sum(is_prime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        import numpy as np\n",
    "        def pri3(n):\n",
    "            a = np.ones(n//2)\n",
    "            for i in range(3,int(n**0.5)+1,2):\n",
    "                if a[i//2]: a[i*i//2::i] = False\n",
    "            return 2*np.nonzero(a)[0][1::]+1\n",
    "        if n==0 or n==1 or n==2:\n",
    "            return 0\n",
    "        else:\n",
    "            return len(pri3(n).tolist())+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 欧式筛，线性筛\n",
    "    # 在埃氏筛基础上的改进，例如 60，在埃氏筛中会被重复多次筛，欧拉筛要求每个合数只需要被其最小的质因子筛掉，即 60 只会被 2 筛掉一次\n",
    "    # 6 = 2 * 2 * 3 = 2 * 6 = 3 * 4，即 6 只会被 2 * 6 筛，而不会被 3 * 4 筛\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        # 注意，第一个无效，这样保证了索引和实际值一致\n",
    "        is_prime_list = [True] * n\n",
    "        is_prime_list[0] = False\n",
    "        is_prime_list[1] = False\n",
    "        prime_list = list()\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if is_prime_list[i]:\n",
    "                prime_list.append(i)\n",
    "            for prime in prime_list:\n",
    "                if i * prime >= n:\n",
    "                    break\n",
    "                is_prime_list[i * prime] = False\n",
    "                # 这里的 break 保证了只会被筛一次，例如 i == 4, prime == 2，就会 break，而不会进行下一次 i == 4, prime == 3\n",
    "                # 因为 12 要被最小质因子 prime == 2，即等待 i = 6 的时候筛掉，而不是提前被 prime == 3 筛掉\n",
    "                if i % prime == 0:\n",
    "                    break\n",
    "        prime_count = 0\n",
    "        for value in is_prime_list:\n",
    "            if value:\n",
    "                prime_count += 1\n",
    "        return prime_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 5*10**6\n",
    "isPrimes = [1] * (n // 2)  # 所有2的倍数扔掉，缺1个2，多一个1，抵消\n",
    "for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "    if isPrimes[i // 2] == 1:\n",
    "        isPrimes[(i//2)+i*(i//2)::i] = [0] * ceil((n//2-(i//2)-i*(i//2))/i)\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        return isPrimes[:n//2].count(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from array import array\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        isPrime = array('b', [True] * n)\n",
    "        isPrime[0] = isPrime[1] = False\n",
    "        for i in range(2, isqrt(n) + 1):\n",
    "            if isPrime[i]:\n",
    "                if i * i < n:\n",
    "                    isPrime[i * i: n: i] = array('b', [False] * ((n - 1) // i - i + 1))\n",
    "        return len([i for i, x in enumerate(isPrime) if x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m = 5*10**6+1\n",
    "dp = [True]*m\n",
    "for i in range(2,m//2):\n",
    "    if dp[i] == False:\n",
    "        continue\n",
    "    for j in range(i+i,m,i):\n",
    "        dp[j] = False\n",
    "cnt = 0\n",
    "dp[0] = dp[1] = 0\n",
    "for i in range(2,m):\n",
    "    if dp[i]:\n",
    "        dp[i] = dp[i-1] + 1\n",
    "    else:\n",
    "        dp[i] = dp[i-1]\n",
    "#print(f'0-{m}内共有 {cnt-1}个质数')\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        #print(dp)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int)-> int:\n",
    "        s = []\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        rang = [True] * n\n",
    "        count = 0\n",
    "        for i in range(2, n):\n",
    "            if rang[i]:\n",
    "                s.append(i)\n",
    "                count = count + 1\n",
    "            j = 0\n",
    "            while j < count and s[j] * i < n:\n",
    "                rang[s[j] * i] = False\n",
    "                if i % s[j] == 0:\n",
    "                    break\n",
    "                j += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        MX = n\n",
    "        prime = []\n",
    "        is_prime = [True] * MX\n",
    "        for i in range(2,MX):\n",
    "            if is_prime[i]:\n",
    "                prime.append(i)\n",
    "            for j in range(i*i,MX,i): #2是质数，划掉2的倍数，从2的平方开始，3是质数，划掉3的倍数，从3的平方开始\n",
    "                is_prime[j]=False\n",
    "        return len(prime)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 5 *(10**6)+1\n",
    "is_prime = [1]*mx \n",
    "primes = []\n",
    "for i in range(2, mx):\n",
    "    # 将质数的倍数标记为合数\n",
    "    if is_prime[i]:\n",
    "        # count += 1\n",
    "        # 从 i*i 开始标记\n",
    "        for j in range(i*i, mx, i):\n",
    "            is_prime[j] = 0\n",
    "        primes.append(i) \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        return bisect.bisect_left(primes,n)\n",
    "     # 定义数组标记是否是质数\n",
    "        # is_prime = [1] * n\n",
    "        \n",
    "        # count = 0\n",
    "        # for i in range(2, n):\n",
    "        #     # 将质数的倍数标记为合数\n",
    "        #     if is_prime[i]:\n",
    "        #         count += 1\n",
    "        #         # 从 i*i 开始标记\n",
    "        #         for j in range(i*i, n, i):\n",
    "        #             is_prime[j] = 0\n",
    "\n",
    "\n",
    "        # def isprimes(x):\n",
    "        #     i = 2\n",
    "        #     while i*i<=x:\n",
    "        #         if x%i ==0:\n",
    "        #             return False\n",
    "        #         i += 1\n",
    "        #     return True\n",
    "        # ans = 0\n",
    "        # for i in range(2,n):\n",
    "        #     if isprimes(i):\n",
    "        #         ans += 1\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        if n == 0 or n == 1 or n == 2:\n",
    "            return 0\n",
    "\n",
    "        lst_prime = []\n",
    "        lst_not_prime = [0] * (5 * (10 ** 6))\n",
    "\n",
    "        for i in range(2, n):\n",
    "            if lst_not_prime[i] == 0:\n",
    "                lst_prime.append(i)\n",
    "                for j in range(i*i, n, i):\n",
    "                    lst_not_prime[j] = 1\n",
    "        \n",
    "        return len(lst_prime)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:  # handle edge cases\n",
    "            return 0\n",
    "        \n",
    "        isPrime = [1] * n\n",
    "        ans = 0\n",
    "        \n",
    "        for i in range(2, n):\n",
    "            if isPrime[i]:\n",
    "                ans += 1\n",
    "                if i * i < n:\n",
    "                    for j in range(i * i, n, i):\n",
    "                        isPrime[j] = 0\n",
    "                        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        arr=np.ones(n)\n",
    "        arr[:2]=0\n",
    "        for i in range(n):\n",
    "            if arr[i]:\n",
    "                arr[i**2::i]=0\n",
    "        return int(np.sum(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "\n",
    "        # if n <= 2: return 0\n",
    "\n",
    "        # def is_zhi(x):\n",
    "        #     if x < 2:\n",
    "        #         return False\n",
    "        #     for i in range(2, int(x**.5)+1):\n",
    "        #         if x % i == 0:\n",
    "        #             return False\n",
    "        #     return True\n",
    "        \n",
    "        # # print(is_zhi(7))\n",
    "        # cnt = 0\n",
    "        # for i in range(n):\n",
    "        #     is_prime = [True] * (n + 1)\n",
    "        #     if is_zhi(i):\n",
    "        #         print(i)\n",
    "        #         cnt += 1\n",
    "        # return cnt\n",
    "\n",
    "\n",
    "\n",
    "        sign = [1] * n\n",
    "        results = []\n",
    "        for i in range(2, n):\n",
    "            if sign[i]:\n",
    "                results.append(i)\n",
    "                for j in range(2*i, n, i):\n",
    "                    sign[j] = 0\n",
    "        print(results)\n",
    "        return len(results)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        li = [1 for _ in range(n)]\n",
    "        li[0] = 0\n",
    "        li[1] = 0\n",
    "        se = []\n",
    "        for i in range(2, n // 2 + 1):\n",
    "            if li[i]:\n",
    "                se.append(i)\n",
    "            # print(se)\n",
    "            for x in se:\n",
    "                if i * x >= n:\n",
    "                    break\n",
    "                else:\n",
    "                    li[i * x] = 0 \n",
    "                if i % x == 0 and i != x :\n",
    "                    break\n",
    "            # print(li)\n",
    "        # print(li)\n",
    "        return sum(li)\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            if n == 2:\n",
    "                return 0\n",
    "            return 0\n",
    "        res = [True] * n\n",
    "        for i in range(3, int(n ** 0.5) + 1, 2):\n",
    "            res[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)\n",
    "        return len([2] + [i for i in range(3, n, 2) if res[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "N = 6  * 10 ** 6\n",
    "primes = [True] * (N + 1)\n",
    "primes[0] = primes[1] = False\n",
    "p = 2\n",
    "while p * p <= N:\n",
    "    if primes[p]:\n",
    "        for i in range(p * p, N + 1, p): primes[i] = False\n",
    "    p += 1\n",
    "prime_numbers = [i for i, is_prime in enumerate(primes) if is_prime]\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        return bisect_left(prime_numbers, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        def prime(n):\n",
    "            lst = [True] * (n + 1)\n",
    "            for i in range(2,int(n**0.5)+1):\n",
    "                if lst[i]:\n",
    "                    for j in range(i * 2, n + 1, i):\n",
    "                        lst[j] = False\n",
    "            x = [str(i) for i in range(2,n) if lst[i]]\n",
    "            return x\n",
    "        return len(prime(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        list1 = []\n",
    "        natural = [True for P in range(n)]\n",
    "        for P in range(2, n):\n",
    "            if natural[P]:\n",
    "                if P >= 0:\n",
    "                    list1.append(P)\n",
    "                for N in range(P ** 2, n, P):\n",
    "                    natural[N] = False\n",
    "        return len(list1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from array import array\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        min_prime, primes = array('l', range(n + 1)), []\n",
    "        for x in range(2, n):\n",
    "            if min_prime[x] == x: primes.append(x)\n",
    "            for p in primes:\n",
    "                if p > min_prime[x] or (v := x * p) > n: break\n",
    "                min_prime[v] = p\n",
    "        return len(primes)\n",
    "        # isPrime = bytearray([1]) * n\n",
    "        # isPrime[0] = isPrime[1] = 0\n",
    "        # for i in range(2, isqrt(n) + 1):\n",
    "        #     if isPrime[i]:\n",
    "        #         isPrime[i * i: n: i] = bytearray([0]) * ((n - 1) // i - i + 1)\n",
    "        # return sum(isPrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        stack=[]\n",
    "        a=[1 for i in range(n)]\n",
    "        for i in range(2,n):\n",
    "            if a[i]==1:\n",
    "                stack.append(i)\n",
    "            for j in range(len(stack)):\n",
    "                if i*stack[j]<n:\n",
    "                    a[i*stack[j]]=0\n",
    "                else:\n",
    "                    break\n",
    "                if i%stack[j]==0:\n",
    "                    break\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        import numpy as np\n",
    "        def ifzhishu(n):\n",
    "            for i in range(2, int(np.sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            \n",
    "            return True\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        \n",
    "        zhishu = [1 for i in range(n-1)]\n",
    "        for i in range(2,n):\n",
    "            if zhishu[i-1]:\n",
    "                for j in range(i*i, n, i):\n",
    "                        #print(j)\n",
    "                    zhishu[j-1] = 0\n",
    "        #print(zhishu)\n",
    "        return sum(zhishu) - 1\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        else:\n",
    "            r = {2:1}\n",
    "            #ir = math.isqrt(n)\n",
    "            s, e = 2, 4\n",
    "            mk = [1] * (n + 3)\n",
    "            mk[e] = 0\n",
    "            while e < n:\n",
    "                #print(f\"try {s} => {e}\")\n",
    "                for k, v in r.items():\n",
    "                    v += 1\n",
    "                    m = k * v\n",
    "                    while m <= n:\n",
    "                        mk[m] = 0\n",
    "                        v += 1\n",
    "                        m = k * v\n",
    "                    r[k] = v - 1\n",
    "                \n",
    "                t = n\n",
    "                for i in range(s, e + 1):\n",
    "                    if 1 == mk[i]:\n",
    "                        r[i] = 1\n",
    "                        if i * i < n:\n",
    "                            t = i * i\n",
    "                s = e\n",
    "                e = t\n",
    "            for i in range(s, n):\n",
    "                if 1 == mk[i]:\n",
    "                    r[i] = 1\n",
    "            #print(f\"r {r}\")\n",
    "        return len(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from numpy import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        res = [i for i in range(2, n)]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            if res[i] == 0:\n",
    "                continue\n",
    "\n",
    "            times = 2\n",
    "            while res[i] * times - 2 < len(res):\n",
    "                res[res[i] * times - 2] = 0\n",
    "                times += 1\n",
    "\n",
    "        return len(res) - res.count(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "primes = [2, 3, 5, 7]\n",
    "primes_flag = [0, 0, 1]\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        length = len(primes_flag)\n",
    "        if n > length:\n",
    "            primes_flag.extend([1] * (n - length))\n",
    "\n",
    "        count = 0\n",
    "        for i in range(2, n):\n",
    "            if primes_flag[i]:\n",
    "                if i > primes[-1]:\n",
    "                    primes.append(i)\n",
    "                count += 1\n",
    "            for p in primes:\n",
    "                m = i * p\n",
    "                if m >= n:\n",
    "                    break\n",
    "                primes_flag[m] = 0\n",
    "                if i % p == 0:\n",
    "                    break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        prime = [True for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if i == 0 or i == 1:\n",
    "                prime[i] = False\n",
    "                continue\n",
    "            if prime[i] == True:\n",
    "                prime[2 * i: n: i] = [False for _ in range(len(prime[2 * i: n: i]))]\n",
    "        return prime.count(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        else:\n",
    "            prime = [1 if i & 1 else 0 for i in range(n)]\n",
    "            #prime = [1]*n\n",
    "            prime[1],prime[2] = 0, 1\n",
    "            for i in range(3, int(n ** 0.5) + 1):\n",
    "                if prime[i] == 1:\n",
    "                    prime[i * i:n:i] = [0] * len(prime[i * i:n:i])\n",
    "        return sum(prime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n<2:\n",
    "            return 0\n",
    "        isPrime=[1]*n\n",
    "        isPrime[0] = isPrime[1] = 0\n",
    "\n",
    "        for i in range(2,int(n**0.5)+1):\n",
    "            if isPrime[i]:\n",
    "                isPrime[i * i: n: i] = [0] * len(isPrime[i * i: n: i])\n",
    "        return sum(isPrime)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2: return 0\n",
    "        isPrimes = [1] * n\n",
    "        isPrimes[0] = isPrimes[1] = 0\n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "            if isPrimes[i] == 1:\n",
    "                isPrimes[i * i: n: i] = [0] * len(isPrimes[i * i: n: i])\n",
    "        return sum(isPrimes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n<3:return 0\n",
    "        n-=1\n",
    "        x=[0,0]+[1]*(n-1)\n",
    "        z=[2]\n",
    "        for i in range(3,len(x),2):\n",
    "            if x[i]:\n",
    "                for j in [i*k for k in range(i,n//i+1,2) if x[k]]:x[j]=0\n",
    "                z+=[i]\n",
    "        return len(z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n<3:return 0\n",
    "        n,z=n-1,[2]\n",
    "        q,x=(int(math.sqrt(n))+1)|1,[0,0]+[1]*(n-1)\n",
    "        for i in range(3,q,2):\n",
    "            if x[i]:\n",
    "                for j in [i*k for k in range(i,n//i+1,2) if x[k]]:x[j]=0\n",
    "                z+=[i]\n",
    "        for i in range(q,len(x),2):\n",
    "            if x[i]:z+=[i]\n",
    "        return len(z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        s = set()\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        if n == 3:\n",
    "            return 1\n",
    "        num = 3\n",
    "        while num < n:\n",
    "            n_num = num * 3\n",
    "            while n_num < n:\n",
    "                s.add(n_num)\n",
    "                n_num += 2 * num\n",
    "            num += 2\n",
    "        return n//2 - len(s)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        a = [x for x in range(2,n)]\n",
    "        mark = [0 for _ in range(n-2)]\n",
    "        i = 2\n",
    "        while(i*i < n):\n",
    "            if mark[i-2] == 1:\n",
    "                i += 1\n",
    "                continue\n",
    "            t = i*i\n",
    "            while t < n:\n",
    "                if mark[t-2] != 1:\n",
    "                    mark[t-2] = 1\n",
    "                t = t + i\n",
    "            i += 1\n",
    "        count = 0\n",
    "        for i in range(0, n-2):\n",
    "            if mark[i] == 0:\n",
    "                count += 1\n",
    "        return count\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "\n",
    "        visited = set()\n",
    "        ret = 1\n",
    "        for i in range(3, n, 2):\n",
    "            if i not in visited:\n",
    "                ret += 1\n",
    "                visited.add(i)\n",
    "\n",
    "            index = 3\n",
    "            while True:\n",
    "                if i * index < n:\n",
    "                    visited.add(i * index)\n",
    "                else:\n",
    "                    break\n",
    "                index += 2\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        else:\n",
    "            count = 1\n",
    "            d = set()\n",
    "            z = []\n",
    "            for i in range(3, n, 2):\n",
    "                if i not in d:\n",
    "                    count += 1\n",
    "                    z.append(i)\n",
    "\n",
    "                j = 0\n",
    "                while j < len(z) and z[j] * i < n:\n",
    "                    d.add(z[j] * i)\n",
    "                    j += 1\n",
    "            # print(d)\n",
    "            # print(z)\n",
    "\n",
    "            return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n<2:\n",
    "            return 0\n",
    "        isPrimer=[1]*n\n",
    "        isPrimer[0]=isPrimer[1]=0\n",
    "        for i in range(2,int(n**0.5)+1):\n",
    "            if isPrimer[i]:\n",
    "                isPrimer[i*i:n:i]=[0]*((n-1-i*i)//i+1)\n",
    "        return sum(isPrimer)\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return 0 \n",
    "        \n",
    "        isPrime = [1] * n \n",
    "        isPrime[0] = isPrime[1] = False \n",
    "\n",
    "        for i in range(2, int(n**0.5) + 1):\n",
    "            if isPrime[i]:\n",
    "                isPrime[i*i : n : i] = [0] * ((n- i*i - 1) // i + 1)\n",
    "        \n",
    "        return sum(isPrime)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
